SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Multi-armed bandit</title>

</head>

Multi-armed bandit

</h1>

</header>

In <a href="Probability_theory" title="Probability theory">probability theory</a> and <a href="Machine_learning" title="Machine learning">machine learning</a>, the multi-armed bandit problem (sometimes called the K-<a href="#cite_note-Auer2002-1">[1]</a> or N-armed bandit problem<a href="#cite_note-2">[2]</a>) is named from imagining a <a href="Gambler" class="mw-redirect" title="Gambler">gambler</a> at a row of <a href="Slot_machines" class="mw-redirect" title="Slot machines">slot machines</a> (sometimes known as "<a href="https://en.wiktionary.org/wiki/one-armed_bandit" class="extiw external" title="wikt:one-armed bandit">one-armed bandits</a>"), who has to decide which machines to play, how many times to play each machine and in which order to play them, and whether to continue with the current machine or try a different machine.<a href="#cite_note-weber-3">[3]</a>

More generally, it is a problem in which a decision maker iteratively selects one of multiple fixed choices (i.e., arms or actions) when the properties of each choice are only partially known at the time of allocation, and may become better understood as time passes. A fundamental aspect of bandit problems is that choosing an arm does not affect the properties of the arm or other arms.<a href="#cite_note-4">[4]</a>

Instances of the multi-armed bandit problem include the task of iteratively allocating a fixed, limited set of resources between competing (alternative) choices in a way that minimizes the <a href="Regret_(decision_theory)" title="Regret (decision theory)">regret</a>.<a href="#cite_note-Gittins89-5">[5]</a><a href="#cite_note-BF-6">[6]</a> A notable alternative setup for the multi-armed bandit problem includes the "best arm identification (BAI)" problem where the goal is instead to identify the best choice by the end of a finite number of rounds.<a href="#cite_note-7">[7]</a>

The multi-armed bandit problem is a classic <a href="Reinforcement_learning" title="Reinforcement learning">reinforcement learning</a> problem that exemplifies the <a href="Exploration%E2%80%93exploitation_dilemma" title="Exploration–exploitation dilemma">exploration–exploitation tradeoff dilemma</a>. In contrast to general reinforcement learning, the selected actions in bandit problems do not affect the reward distribution of the arms.

The multi-armed bandit problem also falls into the broad category of <a href="Stochastic_scheduling" title="Stochastic scheduling">stochastic scheduling</a>.

In the problem, each machine provides a random reward from a <a href="Probability_distribution" title="Probability distribution">probability distribution</a> specific to that machine, that is not known a priori. The objective of the gambler is to maximize the sum of rewards earned through a sequence of lever pulls.<a href="#cite_note-Gittins89-5">[5]</a><a href="#cite_note-BF-6">[6]</a> The crucial tradeoff the gambler faces at each trial is between "exploitation" of the machine that has the highest expected payoff and "exploration" to get more <a href="Bayes'_theorem" title="Bayes' theorem">information</a> about the expected payoffs of the other machines. The trade-off between exploration and exploitation is also faced in machine learning. In practice, multi-armed bandits have been used to model problems such as managing research projects in a large organization, like a science foundation or a <a href="Pharmaceutical_company" class="mw-redirect" title="Pharmaceutical company">pharmaceutical company</a>.<a href="#cite_note-Gittins89-5">[5]</a><a href="#cite_note-BF-6">[6]</a> In early versions of the problem, the gambler begins with no initial knowledge about the machines.

<a href="Herbert_Robbins" title="Herbert Robbins">Herbert Robbins</a> in 1952, realizing the importance of the problem, constructed convergent population selection strategies in "some aspects of the sequential design of experiments".<a href="#cite_note-8">[8]</a> A theorem, the <a href="Gittins_index" title="Gittins index">Gittins index</a>, first published by <a href="John_C._Gittins" title="John C. Gittins">John C. Gittins</a>, gives an optimal policy for maximizing the expected discounted reward.<a href="#cite_note-Gittins1979-9">[9]</a>

<div class="mw-heading mw-heading2"><h2 id="Empirical_motivation">Empirical motivation</h2></div>

The multi-armed bandit problem models an agent that simultaneously attempts to acquire new knowledge (called "exploration") and optimize their decisions based on existing knowledge (called "exploitation"). The agent attempts to balance these competing tasks in order to maximize their total value over the period of time considered. There are many practical applications of the bandit model, for example:

<ul><li><a href="Clinical_trial" title="Clinical trial">clinical trials</a> investigating the effects of different experimental treatments while minimizing patient losses,<a href="#cite_note-Gittins89-5">[5]</a><a href="#cite_note-BF-6">[6]</a><a href="#cite_note-WHP-10">[10]</a><a href="#cite_note-KD-11">[11]</a></li>

<li><a href="Adaptive_routing" class="mw-redirect" title="Adaptive routing">adaptive routing</a> efforts for minimizing delays in a network,</li>

<li><a href="Portfolio_(finance)" title="Portfolio (finance)">financial portfolio design</a><a href="#cite_note-BrochuHoffmandeFreitas-12">[12]</a><a href="#cite_note-ShenWangJiangZha-13">[13]</a></li></ul>

In these practical examples, the problem requires balancing reward maximization based on the knowledge already acquired with attempting new actions to further increase knowledge. This is known as the exploitation vs. exploration tradeoff in <a href="Machine_learning" title="Machine learning">machine learning</a>.

The model has also been used to control dynamic allocation of resources to different projects, answering the question of which project to work on, given uncertainty about the difficulty and payoff of each possibility.<a href="#cite_note-farias2011irrevocable-14">[14]</a>

Originally considered by Allied scientists in <a href="World_War_II" title="World War II">World War II</a>, it proved so intractable that, according to <a href="Peter_Whittle_(mathematician)" title="Peter Whittle (mathematician)">Peter Whittle</a>, the problem was proposed to be dropped over <a href="Germany" title="Germany">Germany</a> so that German scientists could also waste their time on it.<a href="#cite_note-Whittle79-15">[15]</a>

The version of the problem now commonly analyzed was formulated by <a href="Herbert_Robbins" title="Herbert Robbins">Herbert Robbins</a> in 1952.

<div class="mw-heading mw-heading2"><h2 id="The_multi-armed_bandit_model">The multi-armed bandit model</h2></div>

The multi-armed bandit (short: bandit or MAB) can be seen as a set of real <a href="Probability_distribution" title="Probability distribution">distributions</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle B=\{R_{1},\dots ,R_{K}\}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle B=\{R_{1},\dots ,R_{K}\}}</annotation>

</semantics>

</math><img src="./e67c275c3f89e55686789c105cfa69f9d4f09859.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.641ex; height:2.843ex;" alt="{\displaystyle B=\{R_{1},\dots ,R_{K}\}}" loading="lazy">, each distribution being associated with the rewards delivered by one of the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K\in \mathbb {N} ^{+}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K\in \mathbb {N} ^{+}}</annotation>

</semantics>

</math><img src="./d90b7afbf12f15744a3b8b2163ccf551ef01a9aa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.095ex; height:2.509ex;" alt="{\displaystyle K\in \mathbb {N} ^{+}}" loading="lazy"> levers. Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mu _{1},\dots ,\mu _{K}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu _{1},\dots ,\mu _{K}}</annotation>

</semantics>

</math><img src="./d2c289c5a590fb89a7cabda5eaa4b69efd2782a2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.729ex; height:2.176ex;" alt="{\displaystyle \mu _{1},\dots ,\mu _{K}}" loading="lazy"> be the mean values associated with these reward distributions. The gambler iteratively plays one lever per round and observes the associated reward. The objective is to maximize the sum of the collected rewards. The horizon <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle H}</annotation>

</semantics>

</math><img src="./75a9edddcca2f782014371f75dca39d7e13a9c1b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle H}" loading="lazy"> is the number of rounds that remain to be played. The bandit problem is formally equivalent to a one-state <a href="Markov_decision_process" title="Markov decision process">Markov decision process</a>. The <a href="Regret_(decision_theory)" title="Regret (decision theory)">regret</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \rho }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \rho }</annotation>

</semantics>

</math><img src="./1f7d439671d1289b6a816e6af7a304be40608d64.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.202ex; height:2.176ex;" alt="{\displaystyle \rho }" loading="lazy"> after <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T}</annotation>

</semantics>

</math><img src="./ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}" loading="lazy"> rounds is defined as the expected difference between the reward sum associated with an optimal strategy and the sum of the collected rewards:

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</munderover>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \rho =T\mu ^{*}-\sum _{t=1}^{T}{\widehat {r}}_{t}}</annotation>

</semantics>

</math><img src="./374d9c4611ca7fff2d61176207a547f16f5877a8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:17.093ex; height:7.343ex;" alt="{\displaystyle \rho =T\mu ^{*}-\sum _{t=1}^{T}{\widehat {r}}_{t}}" loading="lazy">,

where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mu ^{*}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu ^{*}}</annotation>

</semantics>

</math><img src="./670d0d4db6668c13d249c92fb99c34d2a9f236f7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.456ex; height:2.843ex;" alt="{\displaystyle \mu ^{*}}" loading="lazy"> is the maximal reward mean, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mu ^{*}=\max _{k}\{\mu _{k}\}}">

<msup>

</mrow>

</msup>

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu ^{*}=\max _{k}\{\mu _{k}\}}</annotation>

</semantics>

</math><img src="./e39c290f0835d49cc7ad055a1558c92a9473ca20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:14.696ex; height:4.009ex;" alt="{\displaystyle \mu ^{*}=\max _{k}\{\mu _{k}\}}" loading="lazy">, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\widehat {r}}_{t}}">

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\widehat {r}}_{t}}</annotation>

</semantics>

</math><img src="./a9ade3337c1462d0b6b5e25badce32bbf9f8fff5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.118ex; height:2.509ex;" alt="{\displaystyle {\widehat {r}}_{t}}" loading="lazy"> is the reward in round t.

A zero-regret strategy is a strategy whose average regret per round <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \rho /T}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \rho /T}</annotation>

</semantics>

</math><img src="./d840953c8a665b101ddc3b09c702ca89eb6eef39.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.001ex; height:2.843ex;" alt="{\displaystyle \rho /T}" loading="lazy"> tends to zero with probability 1 when the number of played rounds tends to infinity.<a href="#cite_note-Vermorel2005-16">[16]</a> Intuitively, zero-regret strategies are guaranteed to converge to a (not necessarily unique) optimal strategy if enough rounds are played.

<div class="mw-heading mw-heading2"><h2 id="Variations">Variations</h2></div>

A common formulation is the Binary multi-armed bandit or Bernoulli multi-armed bandit, which issues a reward of one with probability <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math><img src="./81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy">, and otherwise a reward of zero.

Another formulation of the multi-armed bandit has each arm representing an independent Markov machine. Each time a particular arm is played, the state of that machine advances to a new one, chosen according to the Markov state evolution probabilities. There is a reward depending on the current state of the machine. In a generalization called the "restless bandit problem", the states of non-played arms can also evolve over time.<a href="#cite_note-Whittle88-17">[17]</a> There has also been discussion of systems where the number of choices (about which arm to play) increases over time.<a href="#cite_note-Whittle81-18">[18]</a>

Computer science researchers have studied multi-armed bandits under worst-case assumptions, obtaining algorithms to minimize regret in both finite and infinite (<a href="Asymptotic" class="mw-redirect" title="Asymptotic">asymptotic</a>) time horizons for both stochastic<a href="#cite_note-Auer2002-1">[1]</a> and non-stochastic<a href="#cite_note-19">[19]</a> arm payoffs.

<div class="mw-heading mw-heading3"><h3 id="Best_arm_identification">Best arm identification</h3></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

An important variation of the classical regret minimization problem in multi-armed bandits is best arm identification (BAI),<a href="#cite_note-Garivier16-20">[20]</a> also known as pure exploration. This problem is crucial in various applications, including clinical trials, adaptive routing, recommendation systems, and A/B testing.

In BAI, the objective is to identify the arm having the highest expected reward. An algorithm in this setting is characterized by a sampling rule, a decision rule, and a stopping rule, described as follows:

<ol><li>Sampling rule: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (a_{t})_{t\geq 1}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (a_{t})_{t\geq 1}}</annotation>

</semantics>

</math><img src="./467ccd9913849c2c699d03ffe72039388c803734.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.792ex; height:2.843ex;" alt="{\displaystyle (a_{t})_{t\geq 1}}" loading="lazy"> is a sequence of actions at each time step</li>

<li>Stopping rule: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \tau }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \tau }</annotation>

</semantics>

</math><img src="./38a7dcde9730ef0853809fefc18d88771f95206c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.202ex; height:1.676ex;" alt="{\displaystyle \tau }" loading="lazy"> is a (random) stopping time which suggests when to stop collecting samples</li>

<li>Decision rule: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\hat {a}}_{\tau }}">

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\hat {a}}_{\tau }}</annotation>

</semantics>

</math><img src="./98a0ddd34635446ae700028aa02b586b382b2218.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.312ex; height:2.509ex;" alt="{\displaystyle {\hat {a}}_{\tau }}" loading="lazy"> is a guess on the best arm based on the data collected up to time <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \tau }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \tau }</annotation>

</semantics>

There are two predominant settings in BAI:

Fixed budget setting: Given a time horizon <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T\geq 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T\geq 1}</annotation>

</semantics>

</math><img src="./fbdc5d45a32ea6dfa3e5fb5cec5d0b88c9146eed.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.897ex; height:2.343ex;" alt="{\displaystyle T\geq 1}" loading="lazy">, the objective is to identify the arm with the highest expected reward <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a^{\star }\in \arg \max _{k}\mu _{k}}">

<msup>

</mrow>

</msup>

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a^{\star }\in \arg \max _{k}\mu _{k}}</annotation>

</semantics>

</math><img src="./17e071b40771e12021e615775452d699432f027a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:15.952ex; height:4.009ex;" alt="{\displaystyle a^{\star }\in \arg \max _{k}\mu _{k}}" loading="lazy"> minimizing probability of error <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \delta }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \delta }</annotation>

</semantics>

</math><img src="./c5321cfa797202b3e1f8620663ff43c4660ea03a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:2.343ex;" alt="{\displaystyle \delta }" loading="lazy">.

Fixed confidence setting: Given a confidence level <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \delta \in (0,1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \delta \in (0,1)}</annotation>

</semantics>

</math><img src="./1ed6a235fdf92c320bbc6b80f3a62e1e9e5a676b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.057ex; height:2.843ex;" alt="{\displaystyle \delta \in (0,1)}" loading="lazy">, the objective is to identify the arm with the highest expected reward <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a^{\star }\in \arg \max _{k}\mu _{k}}">

<msup>

</mrow>

</msup>

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a^{\star }\in \arg \max _{k}\mu _{k}}</annotation>

</semantics>

</math><img src="./17e071b40771e12021e615775452d699432f027a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:15.952ex; height:4.009ex;" alt="{\displaystyle a^{\star }\in \arg \max _{k}\mu _{k}}" loading="lazy"> with the least possible amount of trials and with probability of error <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {P} ({\hat {a}}_{\tau }\neq a^{\star })\leq \delta }">

</mrow>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {P} ({\hat {a}}_{\tau }\neq a^{\star })\leq \delta }</annotation>

</semantics>

</math><img src="./1c0b0b123e9e89682d4791e9f9280a4293f8c08d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.071ex; height:2.843ex;" alt="{\displaystyle \mathbb {P} ({\hat {a}}_{\tau }\neq a^{\star })\leq \delta }" loading="lazy">.

For example using a decision rule, we could use <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m_{1}}</annotation>

</semantics>

</math><img src="./31aafa60e48d39ccce922404c0b80340b2cc777a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.095ex; height:2.009ex;" alt="{\displaystyle m_{1}}" loading="lazy"> where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m}</annotation>

</semantics>

</math><img src="./0a07d98bb302f3856cbabc47b2b9016692e3f7bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.04ex; height:1.676ex;" alt="{\displaystyle m}" loading="lazy"> is the machine no.1 (you can use a different variable respectively) and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1}</annotation>

</semantics>

</math><img src="./92d98b82a3778f043108d4e20960a9193df57cbf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 1}" loading="lazy"> is the amount for each time an attempt is made at pulling the lever, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \int \sum m_{1},m_{2},(...)=M}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \int \sum m_{1},m_{2},(...)=M}</annotation>

</semantics>

</math><img src="./44c4205c54f107833f45274bf5ebd458557bc878.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:25.032ex; height:5.676ex;" alt="{\displaystyle \int \sum m_{1},m_{2},(...)=M}" loading="lazy">, identify <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"> as the sum of each attempts <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m_{1}+m_{2}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m_{1}+m_{2}}</annotation>

</semantics>

</math><img src="./648effd88b01ad99e59e69e7b60809ea505ea337.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.03ex; height:2.343ex;" alt="{\displaystyle m_{1}+m_{2}}" loading="lazy">, (...) as needed, and from there you can get a ratio, sum or mean as quantitative probability and sample your formulation for each slots.

You can also do <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \int \sum _{k\propto _{i}}^{N}-(n_{j})}">

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \int \sum _{k\propto _{i}}^{N}-(n_{j})}</annotation>

</semantics>

</math><img src="./cfc340bd56d14b449fadcb7f1cf5442d2b455c4e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:12.245ex; height:7.676ex;" alt="{\displaystyle \int \sum _{k\propto _{i}}^{N}-(n_{j})}" loading="lazy"> where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m1+m2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m1+m2}</annotation>

</semantics>

</math><img src="./647db8252bccbd8e5fb2ec31bc04fb279b81587e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:9.246ex; height:2.343ex;" alt="{\displaystyle m1+m2}" loading="lazy"> equal to each a unique machine slot, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x,y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x,y}</annotation>

</semantics>

</math><img src="./5ea0abffd33a692ded22accc104515a032851dff.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.519ex; height:2.009ex;" alt="{\displaystyle x,y}" loading="lazy"> is the amount each time the lever is triggered, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"> is the sum of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (m1_{x},_{y})+(m2_{x},_{y})(...)}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (m1_{x},_{y})+(m2_{x},_{y})(...)}</annotation>

</semantics>

</math><img src="./f21c51264f43563b5219bdf15fd05bf6a951304e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:24.287ex; height:3.009ex;" alt="{\displaystyle (m1_{x},_{y})+(m2_{x},_{y})(...)}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> would be the total available amount in your possession, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> is relative to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"> where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N=n(n_{a},b),(n1_{a},b),(n2_{a},b)}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N=n(n_{a},b),(n1_{a},b),(n2_{a},b)}</annotation>

</semantics>

</math><img src="./465467a890c1a81b751aeed59c0fe05ce7d68ae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:29.962ex; height:2.843ex;" alt="{\displaystyle N=n(n_{a},b),(n1_{a},b),(n2_{a},b)}" loading="lazy"> reduced <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n_{j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n_{j}}</annotation>

</semantics>

</math><img src="./d2c97b31dca4eeefe57123a12e69e6ea73f3dcd2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.304ex; height:2.343ex;" alt="{\displaystyle n_{j}}" loading="lazy"> as the sum of each gain or loss from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a,b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a,b}</annotation>

</semantics>

</math><img src="./181523deba732fda302fd176275a0739121d3bc8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.261ex; height:2.509ex;" alt="{\displaystyle a,b}" loading="lazy"> (for example, suppose you have 100$ that is defined as <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math><img src="./ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"> would be a gain, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b}</annotation>

</semantics>

</math><img src="./f11423fbb2e967f986e36804a8ae4271734917c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}" loading="lazy"> is equal to a loss. From there you get your results either positive or negative to add for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"> with your own specific rule) and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"> as the maximum you are willing to spend.

It is possible to express this construction using a combination of multiple algebraic formulation, as mentioned above where you can limit with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T}</annotation>

</semantics>

<div class="mw-heading mw-heading2"><h2 id="Bandit_strategies">Bandit strategies</h2></div>

A major breakthrough was the construction of optimal population selection strategies, or policies (that possess uniformly maximum convergence rate to the population with highest mean) in the work described below.

<div class="mw-heading mw-heading3"><h3 id="Optimal_solutions">Optimal solutions</h3></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">Further information: <a href="Gittins_index" title="Gittins index">Gittins index</a></div>

In the paper "Asymptotically efficient adaptive allocation rules", Lai and Robbins<a href="#cite_note-21">[21]</a> (following papers of Robbins and his co-workers going back to Robbins in the year 1952) constructed convergent population selection policies that possess the fastest rate of convergence (to the population with highest mean) for the case that the population reward distributions are the one-parameter exponential family. Then, in <a href="Michael_Katehakis" title="Michael Katehakis">Katehakis</a> and <a href="Herbert_Robbins" title="Herbert Robbins">Robbins</a><a href="#cite_note-22">[22]</a> simplifications of the policy and the main proof were given for the case of normal populations with known variances. The next notable progress was obtained by Burnetas and <a href="Michael_Katehakis" title="Michael Katehakis">Katehakis</a> in the paper "Optimal adaptive policies for sequential allocation problems",<a href="#cite_note-23">[23]</a> where index based policies with uniformly maximum convergence rate were constructed, under more general conditions that include the case in which the distributions of outcomes from each population depend on a vector of unknown parameters. Burnetas and Katehakis (1996) also provided an explicit solution for the important case in which the distributions of outcomes follow arbitrary (i.e., non-parametric) discrete, univariate distributions.

Later in "Optimal adaptive policies for Markov decision processes"<a href="#cite_note-24">[24]</a> Burnetas and Katehakis studied the much larger model of Markov Decision Processes under partial information, where the transition law and/or the expected one period rewards may depend on unknown parameters. In this work, the authors constructed an explicit form for a class of adaptive policies with uniformly maximum convergence rate properties for the total expected finite horizon reward under sufficient assumptions of finite state-action spaces and irreducibility of the transition law. A main feature of these policies is that the choice of actions, at each state and time period, is based on indices that are inflations of the right-hand side of the estimated average reward optimality equations. These inflations have recently been called the optimistic approach in the work of Tewari and Bartlett,<a href="#cite_note-25">[25]</a> Ortner<a href="#cite_note-26">[26]</a> Filippi, Cappé, and Garivier,<a href="#cite_note-27">[27]</a> and Honda and Takemura.<a href="#cite_note-28">[28]</a>

For Bernoulli multi-armed bandits, Pilarski et al.<a href="#cite_note-Pilarski1-29">[29]</a> studied computation methods of deriving fully optimal solutions (not just asymptotically) using dynamic programming in the paper "Optimal Policy for Bernoulli Bandits: Computation and Algorithm Gauge."<a href="#cite_note-Pilarski1-29">[29]</a> Via indexing schemes, lookup tables, and other techniques, this work provided practically applicable optimal solutions for Bernoulli bandits provided that time horizons and numbers of arms did not become excessively large. Pilarski et al.<a href="#cite_note-Pilarski2-30">[30]</a> later extended this work in "Delayed Reward Bernoulli Bandits: Optimal Policy and Predictive Meta-Algorithm PARDI"<a href="#cite_note-Pilarski2-30">[30]</a> to create a method of determining the optimal policy for Bernoulli bandits when rewards may not be immediately revealed following a decision and may be delayed. This method relies upon calculating expected values of reward outcomes which have not yet been revealed and updating posterior probabilities when rewards are revealed.

When optimal solutions to multi-arm bandit tasks<a href="#cite_note-31">[31]</a> are used to derive the value of animals' choices, the activity of neurons in the amygdala and ventral striatum encodes the values derived from these policies, and can be used to decode when the animals make exploratory versus exploitative choices. Moreover, optimal policies better predict animals' choice behavior than alternative strategies (described below). This suggests that the optimal solutions to multi-arm bandit problems are biologically plausible, despite being computationally demanding.<a href="#cite_note-32">[32]</a>

<div class="mw-heading mw-heading3"><h3 id="Approximate_solutions">Approximate solutions</h3></div>

Many strategies exist which provide an approximate solution to the bandit problem, and can be put into the four broad categories detailed below.

<div class="mw-heading mw-heading4"><h4 id="Semi-uniform_strategies">Semi-uniform strategies</h4></div>

Semi-uniform strategies were the earliest (and simplest) strategies discovered to approximately solve the bandit problem. All those strategies have in common a <a href="Greedy_algorithm" title="Greedy algorithm">greedy</a> behavior where the best lever (based on previous observations) is always pulled except when a (uniformly) random action is taken.

<ul><li>Epsilon-greedy strategy:<a href="#cite_note-33">[33]</a> The best lever is selected for a proportion <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1-\epsilon }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1-\epsilon }</annotation>

</semantics>

</math><img src="./57f9b07affe80ff61cdc4f2e47977c8421a59c73.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:4.947ex; height:2.343ex;" alt="{\displaystyle 1-\epsilon }" loading="lazy"> of the trials, and a lever is selected at random (with uniform probability) for a proportion <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \epsilon }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \epsilon }</annotation>

</semantics>

</math><img src="./c3837cad72483d97bcdde49c85d3b7b859fb3fd2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.944ex; height:1.676ex;" alt="{\displaystyle \epsilon }" loading="lazy">. A typical parameter value might be <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \epsilon =0.1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \epsilon =0.1}</annotation>

</semantics>

</math><img src="./71f42be1fff0327aea7ea21875c1fe08c3336685.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.014ex; height:2.176ex;" alt="{\displaystyle \epsilon =0.1}" loading="lazy">, but this can vary widely depending on circumstances and predilections.</li>

<li>Epsilon-first strategy: A pure exploration phase is followed by a pure exploitation phase. For <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"> trials in total, the exploration phase occupies <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \epsilon N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \epsilon N}</annotation>

</semantics>

</math><img src="./e324e9387177f1d79321b241d810338925072954.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.008ex; height:2.176ex;" alt="{\displaystyle \epsilon N}" loading="lazy"> trials and the exploitation phase <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (1-\epsilon )N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (1-\epsilon )N}</annotation>

</semantics>

</math><img src="./2db747031b50331ca469d363e23f5b1010187f15.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.82ex; height:2.843ex;" alt="{\displaystyle (1-\epsilon )N}" loading="lazy"> trials. During the exploration phase, a lever is randomly selected (with uniform probability); during the exploitation phase, the best lever is always selected.</li>

<li>Epsilon-decreasing strategy: Similar to the epsilon-greedy strategy, except that the value of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \epsilon }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \epsilon }</annotation>

</semantics>

</math><img src="./c3837cad72483d97bcdde49c85d3b7b859fb3fd2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.944ex; height:1.676ex;" alt="{\displaystyle \epsilon }" loading="lazy"> decreases as the experiment progresses, resulting in highly explorative behaviour at the start and highly exploitative behaviour at the finish.</li>

<li>Adaptive epsilon-greedy strategy based on value differences (VDBE): Similar to the epsilon-decreasing strategy, except that epsilon is reduced on basis of the learning progress instead of manual tuning (Tokic, 2010).<a href="#cite_note-Tokic2010-34">[34]</a> High fluctuations in the value estimates lead to a high epsilon (high exploration, low exploitation); low fluctuations to a low epsilon (low exploration, high exploitation). Further improvements can be achieved by a <a href="Softmax" class="mw-redirect" title="Softmax">softmax</a>-weighted action selection in case of exploratory actions (Tokic & Palm, 2011).<a href="#cite_note-TokicPalm2011-35">[35]</a></li>

<li>Adaptive epsilon-greedy strategy based on Bayesian ensembles (Epsilon-BMC): An adaptive epsilon adaptation strategy for reinforcement learning similar to VBDE, with monotone convergence guarantees. In this framework, the epsilon parameter is viewed as the expectation of a posterior distribution weighting a greedy agent (that fully trusts the learned reward) and uniform learning agent (that distrusts the learned reward). This posterior is approximated using a suitable Beta distribution under the assumption of normality of observed rewards. In order to address the possible risk of decreasing epsilon too quickly, uncertainty in the variance of the learned reward is also modeled and updated using a normal-gamma model. (Gimelfarb et al., 2019).<a href="#cite_note-Gimelfarb2019-36">[36]</a></li></ul>

<div class="mw-heading mw-heading4"><h4 id="Probability_matching_strategies">Probability matching strategies</h4></div>

Probability matching strategies reflect the idea that the number of pulls for a given lever should match its actual probability of being the optimal lever. Probability matching strategies are also known as <a href="Thompson_sampling" title="Thompson sampling">Thompson sampling</a> or Bayesian Bandits,<a href="#cite_note-Scott2010-37">[37]</a><a href="#cite_note-cl11thompson-38">[38]</a> and are surprisingly easy to implement if you can sample from the posterior for the mean value of each alternative.

Probability matching strategies also admit solutions to so-called contextual bandit problems.<a href="#cite_note-Scott2010-37">[37]</a>

<div class="mw-heading mw-heading4"><h4 id="Pricing_strategies">Pricing strategies</h4></div>

Pricing strategies establish a price for each lever. For example, as illustrated with the POKER algorithm,<a href="#cite_note-Vermorel2005-16">[16]</a> the price can be the sum of the expected reward plus an estimation of extra future rewards that will gain through the additional knowledge. The lever of highest price is always pulled.

<div class="mw-heading mw-heading2"><h2 id="Contextual_bandit">Contextual bandit</h2></div>

A useful generalization of the multi-armed bandit is the contextual multi-armed bandit. At each iteration an agent still has to choose between arms, but they also see a d-dimensional feature vector, the context vector they can use together with the rewards of the arms played in the past to make the choice of the arm to play. Over time, the learner's aim is to collect enough information about how the context vectors and rewards relate to each other, so that it can predict the next best arm to play by looking at the feature vectors.<a href="#cite_note-Langford2008-39">[39]</a>

<div class="mw-heading mw-heading3"><h3 id="Approximate_solutions_for_contextual_bandit">Approximate solutions for contextual bandit</h3></div>

Many strategies exist that provide an approximate solution to the contextual bandit problem, and can be put into two broad categories detailed below.

<div class="mw-heading mw-heading4"><h4 id="Online_linear_bandits">Online linear bandits</h4></div>

<ul><li>LinUCB (Upper Confidence Bound) algorithm: the authors assume a linear dependency between the expected reward of an action and its context and model the representation space using a set of linear predictors.<a href="#cite_note-lcls10linucb-40">[40]</a><a href="#cite_note-clrs11linucb-41">[41]</a></li>

<li>LinRel (Linear Associative Reinforcement Learning) algorithm: Similar to LinUCB, but utilizes <a href="Singular_value_decomposition" title="Singular value decomposition">singular value decomposition</a> rather than <a href="Ridge_regression" title="Ridge regression">ridge regression</a> to obtain an estimate of confidence.<a href="#cite_note-42">[42]</a><a href="#cite_note-43">[43]</a></li></ul>

<div class="mw-heading mw-heading4"><h4 id="Online_non-linear_bandits">Online non-linear bandits</h4></div>

<ul><li>UCBogram algorithm: The nonlinear reward functions are estimated using a piecewise constant estimator called a regressogram in <a href="Nonparametric_regression" title="Nonparametric regression">nonparametric regression</a>. Then, UCB is employed on each constant piece. Successive refinements of the partition of the context space are scheduled or chosen adaptively.<a href="#cite_note-RigZee10-44">[44]</a><a href="#cite_note-slivkins11-45">[45]</a><a href="#cite_note-PerRig13-46">[46]</a></li>

<li>Generalized linear algorithms: The reward distribution follows a generalized linear model, an extension to linear bandits.<a href="#cite_note-fcgs10glm-47">[47]</a><a href="#cite_note-llz17glm-48">[48]</a><a href="#cite_note-jbnw17glm-49">[49]</a><a href="#cite_note-kzslgb19glm-50">[50]</a></li>

<li>KernelUCB algorithm: a kernelized non-linear version of LinUCB, with efficient implementation and finite-time analysis.<a href="#cite_note-Valko2014-51">[51]</a></li>

<li>Bandit Forest algorithm: a <a href="Random_forest" title="Random forest">random forest</a> is built and analyzed w.r.t the random forest built knowing the joint distribution of contexts and rewards.<a href="#cite_note-52">[52]</a></li>

<li>Oracle-based algorithm: The algorithm reduces the contextual bandit problem into a series of supervised learning problem, and does not rely on typical realizability assumption on the reward function.<a href="#cite_note-minimonster-53">[53]</a></li></ul>

<div class="mw-heading mw-heading3"><h3 id="Constrained_contextual_bandit">Constrained contextual bandit</h3></div>

In practice, there is usually a cost associated with the resource consumed by each action and the total cost is limited by a budget in many applications such as crowdsourcing and clinical trials. Constrained contextual bandit (CCB) is such a model that considers both the time and budget constraints in a multi-armed bandit setting.

A. Badanidiyuru et al.<a href="#cite_note-Badanidiyuru2014COLT-54">[54]</a> first studied contextual bandits with budget constraints, also referred to as Resourceful Contextual Bandits, and show that a <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O({\sqrt {T}})}">

<msqrt>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O({\sqrt {T}})}</annotation>

</semantics>

</math><img src="./b08c799ec97aa1891429c5deea1bea86b1c8701e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.155ex; height:3.176ex;" alt="{\displaystyle O({\sqrt {T}})}" loading="lazy"> regret is achievable. However, their work focuses on a finite set of policies, and the algorithm is computationally inefficient.

A simple algorithm with logarithmic regret is proposed in:<a href="#cite_note-Wu2015UCBALP-55">[55]</a>

<ul><li>UCB-ALP algorithm: The framework of UCB-ALP is shown in the right figure. UCB-ALP is a simple algorithm that combines the UCB method with an Adaptive Linear Programming (ALP) algorithm, and can be easily deployed in practical systems. It is the first work that show how to achieve logarithmic regret in constrained contextual bandits. Although<a href="#cite_note-Wu2015UCBALP-55">[55]</a> is devoted to a special case with single budget constraint and fixed cost, the results shed light on the design and analysis of algorithms for more general CCB problems.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Adversarial_bandit">Adversarial bandit</h2></div>

Another variant of the multi-armed bandit problem is called the adversarial bandit, first introduced by Auer and Cesa-Bianchi (1998). In this variant, at each iteration, an agent chooses an arm and an adversary simultaneously chooses the payoff structure for each arm. This is one of the strongest generalizations of the bandit problem<a href="#cite_note-56">[56]</a> as it removes all assumptions of the distribution and a solution to the adversarial bandit problem is a generalized solution to the more specific bandit problems.

<div class="mw-heading mw-heading3"><h3 id="Example:_Iterated_prisoner's_dilemma">Example: Iterated prisoner's dilemma</h3></div>

An example often considered for adversarial bandits is the <a href="Iterated_prisoner's_dilemma" class="mw-redirect" title="Iterated prisoner's dilemma">iterated prisoner's dilemma</a>. In this example, each adversary has two arms to pull. They can either Deny or Confess. Standard stochastic bandit algorithms don't work very well with these iterations. For example, if the opponent cooperates in the first 100 rounds, defects for the next 200, then cooperate in the following 300, etc. then algorithms such as UCB won't be able to react very quickly to these changes. This is because after a certain point sub-optimal arms are rarely pulled to limit exploration and focus on exploitation. When the environment changes the algorithm is unable to adapt or may not even detect the change.

<div class="mw-heading mw-heading3"><h3 id="Approximate_solutions_2">Approximate solutions</h3></div>

Source:<a href="#cite_note-57">[57]</a>

EXP3 is a popular algorithm for adversarial multiarmed bandits, suggested and analyzed in this setting by Auer et al. [2002b].

Recently there was an increased interest in the performance of this algorithm in the stochastic setting, due to its new applications to stochastic multi-armed bandits with side information [Seldin et al., 2011] and to multi-armed bandits in the mixed stochastic-adversarial setting [Bubeck and Slivkins, 2012].

The paper presented an empirical evaluation and improved analysis of the performance of the EXP3 algorithm in the stochastic setting, as well as a modification of the EXP3 algorithm capable of achieving "logarithmic" regret in stochastic environment.

<div class="mw-heading mw-heading5"><h5 id="Algorithm">Algorithm</h5></div>

<pre> Parameters: Real <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \gamma \in (0,1]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \gamma \in (0,1]}</annotation>

</semantics>

</math><img src="./3dc19e2d373af486a2a9fe5dc8c3b749cf5756db.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.013ex; height:2.843ex;" alt="{\displaystyle \gamma \in (0,1]}" loading="lazy">

Initialisation: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \omega _{i}(1)=1}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \omega _{i}(1)=1}</annotation>

</semantics>

</math><img src="./0564ff3a4c0bb900291c1aad0d4e129d3e898a58.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.478ex; height:2.843ex;" alt="{\displaystyle \omega _{i}(1)=1}" loading="lazy"> for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i=1,...,K}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i=1,...,K}</annotation>

</semantics>

</math><img src="./4fcf403a99f3f343092b1b23411804c0c0aa874c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.299ex; height:2.509ex;" alt="{\displaystyle i=1,...,K}" loading="lazy">

For each t = 1, 2, ..., T

1. Set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{i}(t)=(1-\gamma ){\frac {\omega _{i}(t)}{\sum _{j=1}^{K}\omega _{j}(t)}}+{\frac {\gamma }{K}}}">

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

<mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

<mfrac>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{i}(t)=(1-\gamma ){\frac {\omega _{i}(t)}{\sum _{j=1}^{K}\omega _{j}(t)}}+{\frac {\gamma }{K}}}</annotation>

</semantics>

</math><img src="./756c21a40b9c67c466703186086edc3ac00ddde6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; margin-left: -0.089ex; width:32.315ex; height:7.343ex;" alt="{\displaystyle p_{i}(t)=(1-\gamma ){\frac {\omega _{i}(t)}{\sum _{j=1}^{K}\omega _{j}(t)}}+{\frac {\gamma }{K}}}" loading="lazy">       <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i=1,...,K}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i=1,...,K}</annotation>

</semantics>

2. Draw <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i_{t}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i_{t}}</annotation>

</semantics>

</math><img src="./6a9d68068946dcbba63e8d588198b5b8af2780f5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.628ex; height:2.509ex;" alt="{\displaystyle i_{t}}" loading="lazy"> randomly according to the probabilities <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{1}(t),...,p_{K}(t)}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{1}(t),...,p_{K}(t)}</annotation>

</semantics>

</math><img src="./93f7ea1bd2b366ff3e9dacd114519f46a04c2bdc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.089ex; width:15.643ex; height:2.843ex;" alt="{\displaystyle p_{1}(t),...,p_{K}(t)}" loading="lazy">

3. Receive reward <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{i_{t}}(t)\in [0,1]}">

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{i_{t}}(t)\in [0,1]}</annotation>

</semantics>

</math><img src="./10e3084214036b354d688f29dfdefb9cddf857a4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.918ex; height:2.843ex;" alt="{\displaystyle x_{i_{t}}(t)\in [0,1]}" loading="lazy">

4. For <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j=1,...,K}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j=1,...,K}</annotation>

</semantics>

</math><img src="./5d0ca231321f3846f765a07d90b9f46d84a77f7a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:12.481ex; height:2.509ex;" alt="{\displaystyle j=1,...,K}" loading="lazy"> set:

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mrow>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

<mtext>otherwise</mtext>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\hat {x}}_{j}(t)={\begin{cases}x_{j}(t)/p_{j}(t)&{\text{if }}j=i_{t}\\0,&{\text{otherwise}}\end{cases}}}</annotation>

</semantics>

</math><img src="./cb3212062c778b0acbd5b64ca1d9fb7a64c7752e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:33.16ex; height:6.176ex;" alt="{\displaystyle {\hat {x}}_{j}(t)={\begin{cases}x_{j}(t)/p_{j}(t)&{\text{if }}j=i_{t}\\0,&{\text{otherwise}}\end{cases}}}" loading="lazy">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \omega _{j}(t+1)=\omega _{j}(t)\exp(\gamma {\hat {x}}_{j}(t)/K)}</annotation>

</semantics>

</math><img src="./960606779c962ce8b6264af0b8a33f9e450aac76.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:32.238ex; height:3.009ex;" alt="{\displaystyle \omega _{j}(t+1)=\omega _{j}(t)\exp(\gamma {\hat {x}}_{j}(t)/K)}" loading="lazy">

</pre>

<div class="mw-heading mw-heading5"><h5 id="Explanation">Explanation</h5></div>

Exp3 chooses an arm at random with probability <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (1-\gamma )}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (1-\gamma )}</annotation>

</semantics>

</math><img src="./82ee9d4dad4648965cadcab0a1f9230988bdb61b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.074ex; height:2.843ex;" alt="{\displaystyle (1-\gamma )}" loading="lazy"> it prefers arms with higher weights (exploit), it chooses with probability <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \gamma }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \gamma }</annotation>

</semantics>

</math><img src="./a223c880b0ce3da8f64ee33c4f0010beee400b1a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.262ex; height:2.176ex;" alt="{\displaystyle \gamma }" loading="lazy"> to uniformly randomly explore. After receiving the rewards the weights are updated. The exponential growth significantly increases the weight of good arms.

<div class="mw-heading mw-heading5"><h5 id="Regret_analysis">Regret analysis</h5></div>

The (external) regret of the Exp3 algorithm is at most

<msqrt>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O({\sqrt {KTlog(K)}})}</annotation>

</semantics>

</math><img src="./1b0065ce60939dfa33c3e35e6ea554cbb9d60f78.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:16.421ex; height:4.843ex;" alt="{\displaystyle O({\sqrt {KTlog(K)}})}" loading="lazy">

<div class="mw-heading mw-heading4"><h4 id="Follow_the_perturbed_leader_(FPL)_algorithm">Follow the perturbed leader (FPL) algorithm</h4></div>

<div class="mw-heading mw-heading5"><h5 id="Algorithm_2">Algorithm</h5></div>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \eta }</annotation>

</semantics>

</math><img src="./e4d701857cf5fbec133eebaf94deadf722537f64.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.169ex; height:2.176ex;" alt="{\displaystyle \eta }" loading="lazy">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \forall i:R_{i}(1)=0}</annotation>

</semantics>

</math><img src="./6d7549d28e1139a2b9ad26aa438e60ac3cf00134.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.829ex; height:2.843ex;" alt="{\displaystyle \forall i:R_{i}(1)=0}" loading="lazy">

For each t = 1,2,...,T

1. For each arm generate a random noise from an exponential distribution <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \forall i:Z_{i}(t)\sim Exp(\eta )}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \forall i:Z_{i}(t)\sim Exp(\eta )}</annotation>

</semantics>

</math><img src="./c9eeb4c5a1ddf67f87ec2a7dd950295ef9259990.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.42ex; height:2.843ex;" alt="{\displaystyle \forall i:Z_{i}(t)\sim Exp(\eta )}" loading="lazy">

2. Pull arm <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle I(t)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle I(t)}</annotation>

</semantics>

</math><img src="./e2434c9d80c34c95e25cc81ba6700f756a29dac5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.821ex; height:2.843ex;" alt="{\displaystyle I(t)}" loading="lazy">: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle I(t)=arg\max _{i}\{R_{i}(t)+Z_{i}(t)\}}">

</mrow>

</munder>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle I(t)=arg\max _{i}\{R_{i}(t)+Z_{i}(t)\}}</annotation>

</semantics>

</math><img src="./5147a4eb45009e98a12f2697095a6745748975d1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:30.44ex; height:4.009ex;" alt="{\displaystyle I(t)=arg\max _{i}\{R_{i}(t)+Z_{i}(t)\}}" loading="lazy">

Add noise to each arm and pull the one with the highest value

3. Update value: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle R_{I(t)}(t+1)=R_{I(t)}(t)+x_{I(t)}(t)}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle R_{I(t)}(t+1)=R_{I(t)}(t)+x_{I(t)}(t)}</annotation>

</semantics>

</math><img src="./9798730b37449d804fe655d64f1e93d0d43bb5cc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:31.548ex; height:3.176ex;" alt="{\displaystyle R_{I(t)}(t+1)=R_{I(t)}(t)+x_{I(t)}(t)}" loading="lazy">

The rest remains the same

</pre>

<div class="mw-heading mw-heading5"><h5 id="Explanation_2">Explanation</h5></div>

We follow the arm that we think has the best performance so far adding exponential noise to it to provide exploration.<a href="#cite_note-58">[58]</a>

<th>FPL

</th></tr>

<tr>

<td>Maintains weights for each arm to calculate pulling probability</td>

<td>Doesn't need to know the pulling probability per arm

</td></tr>

<tr>

<td>Has efficient theoretical guarantees</td>

<td>The standard FPL does not have good theoretical guarantees

</td></tr>

<tr>

<td>Might be computationally expensive (calculating the exponential terms)</td>

<td>Computationally quite efficient

</td></tr></tbody></table>

<div class="mw-heading mw-heading2"><h2 id="Infinite-armed_bandit">Infinite-armed bandit</h2></div>

In the original specification and in the above variants, the bandit problem is specified with a discrete and finite number of arms, often indicated by the variable <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K}</annotation>

</semantics>

</math><img src="./2b76fce82a62ed5461908f0dc8f037de4e3686b0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.066ex; height:2.176ex;" alt="{\displaystyle K}" loading="lazy">. In the infinite armed case, introduced by Agrawal (1995),<a href="#cite_note-59">[59]</a> the "arms" are a continuous variable in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K}</annotation>

</semantics>

<div class="mw-heading mw-heading2"><h2 id="Non-stationary_bandit">Non-stationary bandit</h2></div>

This framework refers to the multi-armed bandit problem in a non-stationary setting (i.e., in presence of <a href="Concept_drift" title="Concept drift">concept drift</a>). In the non-stationary setting, it is assumed that the expected reward for an arm <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"> can change at every time step <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t\in {\mathcal {T}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t\in {\mathcal {T}}}</annotation>

</semantics>

</math><img src="./96b8b08dd997064818370e5546e240e53155d8a4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.616ex; height:2.343ex;" alt="{\displaystyle t\in {\mathcal {T}}}" loading="lazy">: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mu _{t-1}^{k}\neq \mu _{t}^{k}}">

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu _{t-1}^{k}\neq \mu _{t}^{k}}</annotation>

</semantics>

</math><img src="./d558c5ea16bebc6de3d9e01ead138df63dd595f0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:9.917ex; height:3.343ex;" alt="{\displaystyle \mu _{t-1}^{k}\neq \mu _{t}^{k}}" loading="lazy">. Thus, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mu _{t}^{k}}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu _{t}^{k}}</annotation>

</semantics>

</math><img src="./51d7a9d0170577c5f52299660ccb17966f421541.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.49ex; height:3.176ex;" alt="{\displaystyle \mu _{t}^{k}}" loading="lazy"> no longer represents the whole sequence of expected (stationary) rewards for arm <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">. Instead, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mu ^{k}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu ^{k}}</annotation>

</semantics>

</math><img src="./79f768f87ee222ea1c3522e8a793f40c288928eb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.49ex; height:3.176ex;" alt="{\displaystyle \mu ^{k}}" loading="lazy"> denotes the sequence of expected rewards for arm <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">, defined as <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mu ^{k}=\{\mu _{t}^{k}\}_{t=1}^{T}}">

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu ^{k}=\{\mu _{t}^{k}\}_{t=1}^{T}}</annotation>

</semantics>

</math><img src="./1f385699de77bd58f481cce3cb43acfff0442f7c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:13.331ex; height:3.343ex;" alt="{\displaystyle \mu ^{k}=\{\mu _{t}^{k}\}_{t=1}^{T}}" loading="lazy">.<a href="#cite_note-60">[60]</a>

A dynamic oracle represents the optimal policy to be compared with other policies in the non-stationary setting. The dynamic oracle optimises the expected reward at each step <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t\in {\mathcal {T}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t\in {\mathcal {T}}}</annotation>

</semantics>

</math><img src="./96b8b08dd997064818370e5546e240e53155d8a4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.616ex; height:2.343ex;" alt="{\displaystyle t\in {\mathcal {T}}}" loading="lazy"> by always selecting the best arm, with expected reward of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mu _{t}^{*}}">

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mu _{t}^{*}}</annotation>

</semantics>

</math><img src="./61372ce289cd0ff47b03ec6288d1c18af3de42bd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.456ex; height:2.843ex;" alt="{\displaystyle \mu _{t}^{*}}" loading="lazy">. Thus, the cumulative expected reward <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {D}}(T)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {D}}(T)}</annotation>

</semantics>

</math><img src="./2bc74bfab39167aeac87dbc618c9f6a17657c07c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.237ex; height:2.843ex;" alt="{\displaystyle {\mathcal {D}}(T)}" loading="lazy"> for the dynamic oracle at final time step <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T}</annotation>

</semantics>

</mrow>

</mrow>

</mrow>

</munderover>

</mrow>

</mrow>

</msubsup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {D}}(T)=\sum _{t=1}^{T}{\mu _{t}^{*}}.}</annotation>

</semantics>

</math><img src="./c123ce3f75b1e6ce4c321aa9317a0a29197c6744.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:15.181ex; height:7.343ex;" alt="{\displaystyle {\mathcal {D}}(T)=\sum _{t=1}^{T}{\mu _{t}^{*}}.}" loading="lazy">

Hence, the regret <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \rho ^{\pi }(T)}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \rho ^{\pi }(T)}</annotation>

</semantics>

</math><img src="./b8cf16425589288ec5c180ae3d74c3a02ec73874.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.822ex; height:2.843ex;" alt="{\displaystyle \rho ^{\pi }(T)}" loading="lazy"> for policy <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \pi }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \pi }</annotation>

</semantics>

</math><img src="./9be4ba0bb8df3af72e90a0535fabcc17431e540a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.332ex; height:1.676ex;" alt="{\displaystyle \pi }" loading="lazy"> is computed as the difference between <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {D}}(T)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {D}}(T)}</annotation>

</semantics>

</math><img src="./2bc74bfab39167aeac87dbc618c9f6a17657c07c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.237ex; height:2.843ex;" alt="{\displaystyle {\mathcal {D}}(T)}" loading="lazy"> and the cumulative expected reward at step <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T}</annotation>

</semantics>

</math><img src="./ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}" loading="lazy"> for policy <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \pi }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \pi }</annotation>

</semantics>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</munderover>

</mrow>

</mrow>

</msubsup>

</mrow>

</mrow>

</mrow>

</mrow>

</msubsup>

<mrow>

<mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</msubsup>

<mrow>

<mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \rho ^{\pi }(T)=\sum _{t=1}^{T}{\mu _{t}^{*}}-\mathbb {E} _{\pi }^{\mu }\left[\sum _{t=1}^{T}{r_{t}}\right]={\mathcal {D}}(T)-\mathbb {E} _{\pi }^{\mu }\left[\sum _{t=1}^{T}{r_{t}}\right].}</annotation>

</semantics>

</math><img src="./c749ba0bcbea28ae20d0069f5e4a2f93e88dc29c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:53.145ex; height:7.509ex;" alt="{\displaystyle \rho ^{\pi }(T)=\sum _{t=1}^{T}{\mu _{t}^{*}}-\mathbb {E} _{\pi }^{\mu }\left[\sum _{t=1}^{T}{r_{t}}\right]={\mathcal {D}}(T)-\mathbb {E} _{\pi }^{\mu }\left[\sum _{t=1}^{T}{r_{t}}\right].}" loading="lazy">

Garivier and Moulines derive some of the first results with respect to bandit problems where the underlying model can change during play. A number of algorithms were presented to deal with this case, including Discounted UCB<a href="#cite_note-61">[61]</a> and Sliding-Window UCB.<a href="#cite_note-62">[62]</a> A similar approach based on Thompson Sampling algorithm is the f-Discounted-Sliding-Window Thompson Sampling (f-dsw TS)<a href="#cite_note-63">[63]</a> proposed by Cavenaghi et al. The f-dsw TS algorithm exploits a discount factor on the reward history and an arm-related sliding window to contrast concept drift in non-stationary environments. Another work by Burtini et al. introduces a weighted least squares Thompson sampling approach (WLS-TS), which proves beneficial in both the known and unknown non-stationary cases.<a href="#cite_note-64">[64]</a>

<div class="mw-heading mw-heading2"><h2 id="Other_variants">Other variants</h2></div>

Many variants of the problem have been proposed in recent years.

<div class="mw-heading mw-heading3"><h3 id="Dueling_bandit">Dueling bandit</h3></div>

The dueling bandit variant was introduced by Yue et al. (2012)<a href="#cite_note-YueEtAll2012-65">[65]</a> to model the exploration-versus-exploitation tradeoff for relative feedback.

In this variant the gambler is allowed to pull two levers at the same time, but they only get a binary feedback telling which lever provided the best reward. The difficulty of this problem stems from the fact that the gambler has no way of directly observing the reward of their actions.

The earliest algorithms for this problem were InterleaveFiltering<a href="#cite_note-YueEtAll2012-65">[65]</a> and Beat-The-Mean.<a href="#cite_note-Yue2011ICML:BTM-66">[66]</a>

The relative feedback of dueling bandits can also lead to <a href="Condorcet_paradox" title="Condorcet paradox">voting paradoxes</a>. A solution is to take the <a href="Condorcet_winner" class="mw-redirect" title="Condorcet winner">Condorcet winner</a> as a reference.<a href="#cite_note-Urvoy2013ICML:SAVAGE-67">[67]</a>

More recently, researchers have generalized algorithms from traditional MAB to dueling bandits: Relative Upper Confidence Bounds (RUCB),<a href="#cite_note-Zoghi2014ICML:RUCB-68">[68]</a> Relative EXponential weighing (REX3),<a href="#cite_note-Gajane2015ICML:REX3-69">[69]</a>

Copeland Confidence Bounds (CCB),<a href="#cite_note-Zoghi2015NIPS:CDB-70">[70]</a> Relative Minimum Empirical Divergence (RMED),<a href="#cite_note-Komiyama2015COLT:DB-71">[71]</a> and Double Thompson Sampling (DTS).<a href="#cite_note-Wu2016DTS-72">[72]</a>

<div class="mw-heading mw-heading3"><h3 id="Collaborative_bandit">Collaborative bandit</h3></div>

Approaches using multiple bandits that cooperate sharing knowledge in order to better optimize their performance started in 2013 with "A Gang of Bandits",<a href="#cite_note-GOB-73">[73]</a> an algorithm relying on a similarity graph between the different bandit problems to share knowledge. The need of a similarity graph was removed in 2014 by the work on the CLUB algorithm.<a href="#cite_note-GLZ2014CLUB-74">[74]</a> Following this work, several other researchers created algorithms to learn multiple models at the same time under bandit feedback.

For example, COFIBA was introduced by Li and Karatzoglou and Gentile (SIGIR 2016),<a href="#cite_note-LKG2016COFIBA-75">[75]</a> where the classical collaborative filtering, and content-based filtering methods try to learn a static recommendation model given training data.

<div class="mw-heading mw-heading3"><h3 id="Combinatorial_bandit">Combinatorial bandit</h3></div>

The Combinatorial Multiarmed Bandit (CMAB) problem<a href="#cite_note-gai2010learning-76">[76]</a><a href="#cite_note-chen2013combinatorial-77">[77]</a><a href="#cite_note-ontanon2017combinatorial-78">[78]</a> arises when instead of a single discrete variable to choose from, an agent needs to choose values for a set of variables. Assuming each variable is discrete, the number of possible choices per iteration is exponential in the number of variables. Several CMAB settings have been studied in the literature, from settings where the variables are binary<a href="#cite_note-chen2013combinatorial-77">[77]</a> to more general setting where each variable can take an arbitrary set of values.<a href="#cite_note-ontanon2017combinatorial-78">[78]</a>

<ul><li><a href="Gittins_index" title="Gittins index">Gittins index</a> – a powerful, general strategy for analyzing bandit problems.</li>

<li><a href="Greedy_algorithm" title="Greedy algorithm">Greedy algorithm</a></li>

<li><a href="Optimal_stopping" title="Optimal stopping">Optimal stopping</a></li>

<li><a href="Search_theory" title="Search theory">Search theory</a></li>

<li><a href="Stochastic_scheduling" title="Stochastic scheduling">Stochastic scheduling</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFAuerCesa-BianchiFischer2002" class="citation journal cs1">Auer, P.; Cesa-Bianchi, N.; Fischer, P. (2002). <a rel="nofollow" class="external text" href="https://doi.org/10.1023%2FA%3A1013689704352">"Finite-time Analysis of the Multiarmed Bandit Problem"</a>. Machine Learning. 47 (2/3): 235–256. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1023%2FA%3A1013689704352">10.1023/A:1013689704352</a>.</cite>

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> <cite id="CITEREFKatehakisVeinott,_Jr.1987" class="citation journal cs1">Katehakis, Michael N.; Veinott, Jr., Arthur F. (1987). "The Multi-Armed Bandit Problem: Decomposition and Computation". <a href="Mathematics_of_Operations_Research" title="Mathematics of Operations Research">Mathematics of Operations Research</a>. 12 (2): 262–268. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1287%2Fmoor.12.2.262">10.1287/moor.12.2.262</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:656323">656323</a>.</cite>

</li>

<li id="cite_note-weber-3"><a href="#cite_ref-weber_3-0">^</a> <cite id="CITEREFWeber1992" class="citation cs2">Weber, Richard (1992), "On the Gittins index for multiarmed bandits", <a href="Annals_of_Applied_Probability" title="Annals of Applied Probability">Annals of Applied Probability</a>, 2 (4): 1024–1033, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1214%2Faoap%2F1177005588">10.1214/aoap/1177005588</a>, <a href="JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/2959678">2959678</a></cite>

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> <cite id="CITEREFBubeck2012" class="citation journal cs1">Bubeck, Sébastien (2012). "Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems". Foundations and Trends in Machine Learning. 5: 1–122. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1204.5721">1204.5721</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1561%2F2200000024">10.1561/2200000024</a>.</cite>

</li>

<cite id="CITEREFGittins1989" class="citation cs2"><a href="John_C._Gittins" title="John C. Gittins">Gittins, J. C.</a> (1989), Multi-armed bandit allocation indices, Wiley-Interscience Series in Systems and Optimization., Chichester: John Wiley & Sons, Ltd., <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-471-92059-5</bdi></cite>

</li>

<cite id="CITEREFBerryFristedt1985" class="citation cs2"><a href="Don_Berry_(statistician)" title="Don Berry (statistician)">Berry, Donald A.</a>; Fristedt, Bert (1985), Bandit problems: Sequential allocation of experiments, Monographs on Statistics and Applied Probability, London: Chapman & Hall, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-412-24810-8</bdi></cite>

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> <cite id="CITEREFSoareLazaricMunos2014" class="citation arxiv cs1">Soare, Marta; Lazaric, Alessandro; Munos, Rémi (2014). "Best-Arm Identification in Linear Bandits". <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1409.6110">1409.6110</a> [<a rel="nofollow" class="external text" href="https://arxiv.org/archive/cs.LG">cs.LG</a>].</cite>

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> <cite id="CITEREFRobbins1952" class="citation journal cs1">Robbins, H. (1952). <a rel="nofollow" class="external text" href="https://doi.org/10.1090%2FS0002-9904-1952-09620-8">"Some aspects of the sequential design of experiments"</a>. Bulletin of the American Mathematical Society. 58 (5): 527–535. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1090%2FS0002-9904-1952-09620-8">10.1090/S0002-9904-1952-09620-8</a>.</cite>

</li>

<li id="cite_note-Gittins1979-9"><a href="#cite_ref-Gittins1979_9-0">^</a> <cite id="CITEREFJ._C._Gittins1979" class="citation journal cs1"><a href="John_C._Gittins" title="John C. Gittins">J. C. Gittins</a> (1979). "Bandit Processes and Dynamic Allocation Indices". Journal of the Royal Statistical Society. Series B (Methodological). 41 (2): 148–177. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1111%2Fj.2517-6161.1979.tb01068.x">10.1111/j.2517-6161.1979.tb01068.x</a>. <a href="JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/2985029">2985029</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:17724147">17724147</a>.</cite>

</li>

<cite id="CITEREFPress2009" class="citation cs2">Press, William H. (2009), "Bandit solutions provide unified ethical models for randomized clinical trials and comparative effectiveness research", Proceedings of the National Academy of Sciences, 106 (52): 22387–22392, <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2009PNAS..10622387P">2009PNAS..10622387P</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1073%2Fpnas.0912378106">10.1073/pnas.0912378106</a>, <a href="PMC_(identifier)" class="mw-redirect" title="PMC (identifier)">PMC</a> <a rel="nofollow" class="external text" href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2793317">2793317</a>, <a href="PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/20018711">20018711</a>.</cite>

</li>

<li id="cite_note-KD-11"><a href="#cite_ref-KD_11-0">^</a> Press (1986)

</li>

<cite id="CITEREFBrochuHoffmande_Freitas2010" class="citation arxiv cs1">Brochu, Eric; Hoffman, Matthew W.; de Freitas, Nando (September 2010). "Portfolio Allocation for Bayesian Optimization". <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1009.5419">1009.5419</a> [<a rel="nofollow" class="external text" href="https://arxiv.org/archive/cs.LG">cs.LG</a>].</cite>

</li>

<li id="cite_note-ShenWangJiangZha-13"><a href="#cite_ref-ShenWangJiangZha_13-0">^</a> <cite id="CITEREFShenWangJiangZha2015" class="citation cs2">Shen, Weiwei; Wang, Jun; Jiang, Yu-Gang; Zha, Hongyuan (2015), <a rel="nofollow" class="external text" href="https://web.archive.org/web/20211204190610/https://www.aaai.org/ocs/index.php/IJCAI/IJCAI15/paper/viewPDFInterstitial/10972/10798">"Portfolio Choices with Orthogonal Bandit Learning"</a>, Proceedings of International Joint Conferences on Artificial Intelligence (IJCAI2015), archived from <a rel="nofollow" class="external text" href="http://www.aaai.org/ocs/index.php/IJCAI/IJCAI15/paper/viewPDFInterstitial/10972/10798">the original</a> on 2021-12-04, retrieved 2016-03-20</cite>

</li>

<cite id="CITEREFFariasRitesh2011" class="citation cs2">Farias, Vivek F; Ritesh, Madan (2011), "The irrevocable multiarmed bandit problem", <a href="Operations_Research_(journal)" title="Operations Research (journal)">Operations Research</a>, 59 (2): 383–399, <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.380.6983">10.1.1.380.6983</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1287%2Fopre.1100.0891">10.1287/opre.1100.0891</a></cite>

</li>

<cite id="CITEREFWhittle1979" class="citation cs2"><a href="Peter_Whittle_(mathematician)" title="Peter Whittle (mathematician)">Whittle, Peter</a> (1979), "Discussion of Dr Gittins' paper", <a href="Journal_of_the_Royal_Statistical_Society" title="Journal of the Royal Statistical Society">Journal of the Royal Statistical Society</a>, Series B, 41 (2): 148–177, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1111%2Fj.2517-6161.1979.tb01069.x">10.1111/j.2517-6161.1979.tb01069.x</a></cite>

</li>

<cite id="CITEREFVermorelMohri2005" class="citation cs2">Vermorel, Joannes; Mohri, Mehryar (2005), <a rel="nofollow" class="external text" href="http://bandit.sourceforge.net/Vermorel2005poker.pdf">Multi-armed bandit algorithms and empirical evaluation</a> (PDF), In European Conference on Machine Learning, Springer, pp. 437–448</cite>

</li>

<cite id="CITEREFWhittle1988" class="citation cs2"><a href="Peter_Whittle_(mathematician)" title="Peter Whittle (mathematician)">Whittle, Peter</a> (1988), "Restless bandits: Activity allocation in a changing world", Journal of Applied Probability, 25A: 287–298, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.2307%2F3214163">10.2307/3214163</a>, <a href="JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/3214163">3214163</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0974588">0974588</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:202109695">202109695</a></cite>

</li>

<cite id="CITEREFWhittle1981" class="citation cs2"><a href="Peter_Whittle_(mathematician)" title="Peter Whittle (mathematician)">Whittle, Peter</a> (1981), "Arm-acquiring bandits", Annals of Probability, 9 (2): 284–292, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1214%2Faop%2F1176994469">10.1214/aop/1176994469</a></cite>

</li>

<li id="cite_note-19"><a href="#cite_ref-19">^</a> <cite id="CITEREFAuerCesa-BianchiFreundSchapire2002" class="citation journal cs1">Auer, P.; Cesa-Bianchi, N.; Freund, Y.; Schapire, R. E. (2002). "The Nonstochastic Multiarmed Bandit Problem". <a href="SIAM_J._Comput." class="mw-redirect" title="SIAM J. Comput.">SIAM J. Comput.</a> 32 (1): 48–77. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.130.158">10.1.1.130.158</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2FS0097539701398375">10.1137/S0097539701398375</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:13209702">13209702</a>.</cite>

</li>

<cite id="CITEREFAurelien_GarivierEmilie_Kaufmann2016" class="citation arxiv cs1">Aurelien Garivier; Emilie Kaufmann (2016). "Optimal Best Arm Identification with Fixed Confidence". <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1602.04589">1602.04589</a> [<a rel="nofollow" class="external text" href="https://arxiv.org/archive/math.ST">math.ST</a>].</cite>

</li>

<li id="cite_note-21"><a href="#cite_ref-21">^</a> <cite id="CITEREFLaiRobbins1985" class="citation journal cs1">Lai, T.L.; Robbins, H. (1985). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0196-8858%2885%2990002-8">"Asymptotically efficient adaptive allocation rules"</a>. Advances in Applied Mathematics. 6 (1): 4–22. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0196-8858%2885%2990002-8">10.1016/0196-8858(85)90002-8</a>.</cite>

</li>

<li id="cite_note-22"><a href="#cite_ref-22">^</a> <cite id="CITEREFKatehakisRobbins1995" class="citation journal cs1">Katehakis, M.N.; Robbins, H. (1995). <a rel="nofollow" class="external text" href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC41010">"Sequential choice from several populations"</a>. Proceedings of the National Academy of Sciences of the United States of America. 92 (19): 8584–5. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/1995PNAS...92.8584K">1995PNAS...92.8584K</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1073%2Fpnas.92.19.8584">10.1073/pnas.92.19.8584</a>. <a href="PMC_(identifier)" class="mw-redirect" title="PMC (identifier)">PMC</a> <a rel="nofollow" class="external text" href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC41010">41010</a>. <a href="PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/11607577">11607577</a>.</cite>

</li>

<li id="cite_note-23"><a href="#cite_ref-23">^</a> <cite id="CITEREFBurnetasKatehakis1996" class="citation journal cs1">Burnetas, A.N.; Katehakis, M.N. (1996). <a rel="nofollow" class="external text" href="https://doi.org/10.1006%2Faama.1996.0007">"Optimal adaptive policies for sequential allocation problems"</a>. Advances in Applied Mathematics. 17 (2): 122–142. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1006%2Faama.1996.0007">10.1006/aama.1996.0007</a>.</cite>

</li>

<li id="cite_note-24"><a href="#cite_ref-24">^</a> <cite id="CITEREFBurnetasKatehakis1997" class="citation journal cs1">Burnetas, Apostolos N.; <a href="Michael_Katehakis" title="Michael Katehakis">Katehakis, Michael N.</a> (1997). "Optimal adaptive policies for Markov decision processes". <a href="Mathematics_of_Operations_Research" title="Mathematics of Operations Research">Mathematics of Operations Research</a>. 22 (1): 222–255. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1287%2Fmoor.22.1.222">10.1287/moor.22.1.222</a>.</cite>

</li>

<li id="cite_note-25"><a href="#cite_ref-25">^</a> <cite id="CITEREFTewariBartlett2008" class="citation journal cs1">Tewari, A.; Bartlett, P.L. (2008). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20120525122106/http://books.nips.cc/papers/files/nips20/NIPS2007_0673.pdf">"Optimistic linear programming gives logarithmic regret for irreducible MDPs"</a> (PDF). Advances in Neural Information Processing Systems. 20. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.69.5482">10.1.1.69.5482</a>. Archived from <a rel="nofollow" class="external text" href="http://books.nips.cc/papers/files/nips20/NIPS2007_0673.pdf">the original</a> (PDF) on 2012-05-25. Retrieved 2012-10-12.</cite>

</li>

<li id="cite_note-26"><a href="#cite_ref-26">^</a> <cite id="CITEREFOrtner2010" class="citation journal cs1">Ortner, R. (2010). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.tcs.2010.04.005">"Online regret bounds for Markov decision processes with deterministic transitions"</a>. Theoretical Computer Science. 411 (29): 2684–2695. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.tcs.2010.04.005">10.1016/j.tcs.2010.04.005</a>.</cite>

</li>

<li id="cite_note-27"><a href="#cite_ref-27">^</a> Filippi, S. and Cappé, O. and Garivier, A. (2010). "Online regret bounds for Markov decision processes with deterministic transitions", Communication, Control, and Computing (Allerton), 2010 48th Annual Allerton Conference on, pp. 115–122

</li>

<li id="cite_note-28"><a href="#cite_ref-28">^</a> <cite id="CITEREFHondaTakemura2011" class="citation journal cs1">Honda, J.; Takemura, A. (2011). "An asymptotically optimal policy for finite support models in the multi-armed bandit problem". Machine Learning. 85 (3): 361–391. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/0905.2776">0905.2776</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs10994-011-5257-4">10.1007/s10994-011-5257-4</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:821462">821462</a>.</cite>

</li>

<li id="cite_note-Pilarski1-29">^ <a href="#cite_ref-Pilarski1_29-0">a</a> <a href="#cite_ref-Pilarski1_29-1">b</a> <cite id="CITEREFPilarskiPilarskiVarró2021" class="citation journal cs1">Pilarski, Sebastian; Pilarski, Slawomir; Varró, Dániel (February 2021). <a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTAI.2021.3074122">"Optimal Policy for Bernoulli Bandits: Computation and Algorithm Gauge"</a>. IEEE Transactions on Artificial Intelligence. 2 (1): 2–17. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTAI.2021.3074122">10.1109/TAI.2021.3074122</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/2691-4581">2691-4581</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:235475602">235475602</a>.</cite>

</li>

<li id="cite_note-Pilarski2-30">^ <a href="#cite_ref-Pilarski2_30-0">a</a> <a href="#cite_ref-Pilarski2_30-1">b</a> <cite id="CITEREFPilarskiPilarskiVarro2021" class="citation journal cs1">Pilarski, Sebastian; Pilarski, Slawomir; Varro, Daniel (2021). <a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTAI.2021.3117743">"Delayed Reward Bernoulli Bandits: Optimal Policy and Predictive Meta-Algorithm PARDI"</a>. IEEE Transactions on Artificial Intelligence. 3 (2): 152–163. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTAI.2021.3117743">10.1109/TAI.2021.3117743</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/2691-4581">2691-4581</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:247682940">247682940</a>.</cite>

</li>

<li id="cite_note-31"><a href="#cite_ref-31">^</a> <cite id="CITEREFAverbeck2015" class="citation journal cs1">Averbeck, B.B. (2015). <a rel="nofollow" class="external text" href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4376795">"Theory of choice in bandit, information sampling, and foraging tasks"</a>. PLOS Computational Biology. 11 (3): e1004164. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2015PLSCB..11E4164A">2015PLSCB..11E4164A</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1371%2Fjournal.pcbi.1004164">10.1371/journal.pcbi.1004164</a>. <a href="PMC_(identifier)" class="mw-redirect" title="PMC (identifier)">PMC</a> <a rel="nofollow" class="external text" href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4376795">4376795</a>. <a href="PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/25815510">25815510</a>.</cite>

</li>

<li id="cite_note-32"><a href="#cite_ref-32">^</a> <cite id="CITEREFCostaAverbeck2019" class="citation journal cs1">Costa, V.D.; Averbeck, B.B. (2019). <a rel="nofollow" class="external text" href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6687547">"Subcortical Substrates of Explore-Exploit Decisions in Primates"</a>. Neuron. 103 (3): 533–535. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.neuron.2019.05.017">10.1016/j.neuron.2019.05.017</a>. <a href="PMC_(identifier)" class="mw-redirect" title="PMC (identifier)">PMC</a> <a rel="nofollow" class="external text" href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6687547">6687547</a>. <a href="PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/31196672">31196672</a>.</cite>

</li>

<li id="cite_note-33"><a href="#cite_ref-33">^</a> Sutton, R. S. & Barto, A. G. 1998 Reinforcement learning: an introduction. Cambridge, MA: MIT Press.

</li>

<cite id="CITEREFTokic2010" class="citation cs2">Tokic, Michel (2010), <a rel="nofollow" class="external text" href="http://www.tokic.com/www/tokicm/publikationen/papers/AdaptiveEpsilonGreedyExploration.pdf">"Adaptive ε-greedy exploration in reinforcement learning based on value differences"</a> (PDF), KI 2010: Advances in Artificial Intelligence, Lecture Notes in Computer Science, vol. 6359, Springer-Verlag, pp. 203–210, <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.458.464">10.1.1.458.464</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-642-16111-7_23">10.1007/978-3-642-16111-7_23</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-642-16110-0</bdi></cite>.

</li>

<cite id="CITEREFTokicPalm2011" class="citation cs2">Tokic, Michel; Palm, Günther (2011), <a rel="nofollow" class="external text" href="http://www.tokic.com/www/tokicm/publikationen/papers/KI2011.pdf">"Value-Difference Based Exploration: Adaptive Control Between Epsilon-Greedy and Softmax"</a> (PDF), KI 2011: Advances in Artificial Intelligence, Lecture Notes in Computer Science, vol. 7006, Springer-Verlag, pp. 335–346, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-642-24455-1</bdi></cite>.

</li>

<cite id="CITEREFGimelfarbSannerLee2019" class="citation cs2">Gimelfarb, Michel; Sanner, Scott; Lee, Chi-Guhn (2019), <a rel="nofollow" class="external text" href="http://auai.org/uai2019/proceedings/papers/162.pdf">"ε-BMC: A Bayesian Ensemble Approach to Epsilon-Greedy Exploration in Model-Free Reinforcement Learning"</a> (PDF), Proceedings of the Thirty-Fifth Conference on Uncertainty in Artificial Intelligence, AUAI Press, p. 162</cite>.

</li>

<cite id="CITEREFScott2010" class="citation cs2">Scott, S.L. (2010), "A modern Bayesian look at the multi-armed bandit", Applied Stochastic Models in Business and Industry, 26 (2): 639–658, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1002%2Fasmb.874">10.1002/asmb.874</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:573750">573750</a></cite>

</li>

<cite id="CITEREFOlivier_ChapelleLihong_Li2011" class="citation cs2">Olivier Chapelle; Lihong Li (2011), <a rel="nofollow" class="external text" href="http://papers.nips.cc/paper/4321-an-empirical-evaluation-of-thompson-sampling">"An empirical evaluation of Thompson sampling"</a>, Advances in Neural Information Processing Systems, 24, Curran Associates: 2249–2257</cite>

</li>

<cite id="CITEREFLangfordZhang2008" class="citation cs2">Langford, John; Zhang, Tong (2008), <a rel="nofollow" class="external text" href="http://papers.nips.cc/paper/3178-the-epoch-greedy-algorithm-for-multi-armed-bandits-with-side-information">"The Epoch-Greedy Algorithm for Contextual Multi-armed Bandits"</a>, Advances in Neural Information Processing Systems, vol. 20, Curran Associates, Inc., pp. 817–824</cite>

</li>

<cite id="CITEREFLihong_LiWei_ChuJohn_LangfordRobert_E._Schapire2010" class="citation cs2">Lihong Li; Wei Chu; John Langford; Robert E. Schapire (2010), "A contextual-bandit approach to personalized news article recommendation", Proceedings of the 19th international conference on World wide web, pp. 661–670, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1003.0146">1003.0146</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1772690.1772758">10.1145/1772690.1772758</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9781605587998</bdi>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:207178795">207178795</a></cite>

</li>

<cite id="CITEREFWei_ChuLihong_LiLev_ReyzinRobert_E._Schapire2011" class="citation cs2">Wei Chu; Lihong Li; Lev Reyzin; Robert E. Schapire (2011), <a rel="nofollow" class="external text" href="http://proceedings.mlr.press/v15/chu11a/chu11a.pdf">"Contextual bandits with linear payoff functions"</a> (PDF), Proceedings of the 14th International Conference on Artificial Intelligence and Statistics (AISTATS): 208–214</cite>

</li>

<li id="cite_note-42"><a href="#cite_ref-42">^</a> <cite id="CITEREFAuer2000" class="citation conference cs1">Auer, P. (2000). "Using upper confidence bounds for online learning". Proceedings 41st Annual Symposium on Foundations of Computer Science. IEEE Comput. Soc. pp. 270–279. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2Fsfcs.2000.892116">10.1109/sfcs.2000.892116</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0769508504</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:28713091">28713091</a>.</cite>

</li>

<li id="cite_note-43"><a href="#cite_ref-43">^</a> <cite id="CITEREFHongSongChiu2011" class="citation book cs1">Hong, Tzung-Pei; Song, Wei-Ping; Chiu, Chu-Tien (November 2011). "Evolutionary Composite Attribute Clustering". 2011 International Conference on Technologies and Applications of Artificial Intelligence. IEEE. pp. 305–308. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2Ftaai.2011.59">10.1109/taai.2011.59</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9781457721748</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:14125100">14125100</a>.</cite>

</li>

<cite id="CITEREFRigolletZeevi2010" class="citation cs2">Rigollet, Philippe; Zeevi, Assaf (2010), Nonparametric Bandits with Covariates, Conference on Learning Theory, COLT 2010, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1003.1630">1003.1630</a>, <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2010arXiv1003.1630R">2010arXiv1003.1630R</a></cite>

</li>

<cite id="CITEREFSlivkins2011" class="citation cs2">Slivkins, Aleksandrs (2011), <a rel="nofollow" class="external text" href="http://www.jmlr.org/papers/volume15/slivkins14a/slivkins14a.pdf">Contextual bandits with similarity information.</a> (PDF), Conference on Learning Theory, COLT 2011</cite>

</li>

<cite id="CITEREFPerchetRigollet2013" class="citation cs2">Perchet, Vianney; Rigollet, Philippe (2013), "The multi-armed bandit problem with covariates", <a href="Annals_of_Statistics" title="Annals of Statistics">Annals of Statistics</a>, 41 (2): 693–721, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1110.6084">1110.6084</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1214%2F13-aos1101">10.1214/13-aos1101</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:14258665">14258665</a></cite>

</li>

<cite id="CITEREFSarah_FilippiOlivier_CappéAurélien_GarivierCsaba_Szepesvári2010" class="citation cs2">Sarah Filippi; Olivier Cappé; Aurélien Garivier; Csaba Szepesvári (2010), <a rel="nofollow" class="external text" href="http://papers.nips.cc/paper/4166-parametric-bandits-the-generalized-linear-case">"Parametric Bandits: The Generalized Linear Case"</a>, Advances in Neural Information Processing Systems, 23, Curran Associates: 586–594</cite>

</li>

<cite id="CITEREFLihong_LiYu_LuDengyong_Zhou2017" class="citation cs2">Lihong Li; Yu Lu; Dengyong Zhou (2017), <a rel="nofollow" class="external text" href="http://proceedings.mlr.press/v70/li17c.html">"Provably optimal algorithms for generalized linear contextual bandits"</a>, Proceedings of the 34th International Conference on Machine Learning: 2071–2080, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1703.00048">1703.00048</a>, <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2017arXiv170300048L">2017arXiv170300048L</a></cite>

</li>

<cite id="CITEREFKwang-Sung_JunAniruddha_BhargavaRobert_D._NowakRebecca_Willett2017" class="citation cs2">Kwang-Sung Jun; Aniruddha Bhargava; Robert D. Nowak; Rebecca Willett (2017), <a rel="nofollow" class="external text" href="http://papers.nips.cc/paper/6615-scalable-generalized-linear-bandits-online-computation-and-hashing">"Scalable generalized linear bandits: Online computation and hashing"</a>, Advances in Neural Information Processing Systems, 30, Curran Associates: 99–109, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1706.00136">1706.00136</a>, <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2017arXiv170600136J">2017arXiv170600136J</a></cite>

</li>

<cite id="CITEREFBranislav_KvetonManzil_ZaheerCsaba_SzepesváriLihong_Li2020" class="citation cs2">Branislav Kveton; Manzil Zaheer; Csaba Szepesvári; Lihong Li; Mohammad Ghavamzadeh; Craig Boutilier (2020), "Randomized exploration in generalized linear bandits", Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics (AISTATS), <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1906.08947">1906.08947</a>, <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2019arXiv190608947K">2019arXiv190608947K</a></cite>

</li>

<cite id="CITEREFMichal_ValkoNathan_KordaRémi_MunosIlias_Flaounas2013" class="citation cs2">Michal Valko; Nathan Korda; Rémi Munos; Ilias Flaounas; Nello Cristianini (2013), Finite-Time Analysis of Kernelised Contextual Bandits, 29th Conference on Uncertainty in Artificial Intelligence (UAI 2013) and (JFPDA 2013)., <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1309.6869">1309.6869</a>, <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2013arXiv1309.6869V">2013arXiv1309.6869V</a></cite>

</li>

<li id="cite_note-52"><a href="#cite_ref-52">^</a> <cite id="CITEREFFéraudAllesiardoUrvoyClérot2016" class="citation journal cs1">Féraud, Raphaël; Allesiardo, Robin; Urvoy, Tanguy; Clérot, Fabrice (2016). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20160810224419/http://jmlr.org/proceedings/papers/v51/feraud16.html">"Random Forest for the Contextual Bandit Problem"</a>. Aistats: 93–101. Archived from <a rel="nofollow" class="external text" href="http://jmlr.org/proceedings/papers/v51/feraud16.html">the original</a> on 2016-08-10. Retrieved 2016-06-10.</cite>

</li>

<cite id="CITEREFAlekh_AgarwalDaniel_J._HsuSatyen_KaleJohn_Langford2014" class="citation cs2">Alekh Agarwal; Daniel J. Hsu; Satyen Kale; John Langford; Lihong Li; Robert E. Schapire (2014), <a rel="nofollow" class="external text" href="http://proceedings.mlr.press/v32/agarwalb14.html">"Taming the monster: A fast and simple algorithm for contextual bandits"</a>, Proceedings of the 31st International Conference on Machine Learning: 1638–1646, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1402.0555">1402.0555</a>, <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2014arXiv1402.0555A">2014arXiv1402.0555A</a></cite>

</li>

<li id="cite_note-Badanidiyuru2014COLT-54"><a href="#cite_ref-Badanidiyuru2014COLT_54-0">^</a> <cite id="CITEREFBadanidiyuruLangfordSlivkins2014" class="citation cs2">Badanidiyuru, A.; Langford, J.; Slivkins, A. (2014), <a rel="nofollow" class="external text" href="http://www.jmlr.org/proceedings/papers/v35/badanidiyuru14.pdf">"Resourceful contextual bandits"</a> (PDF), Proceeding of Conference on Learning Theory (COLT)</cite>

</li>

<cite id="CITEREFWuSrikantLiuJiang2015" class="citation cs2">Wu, Huasen; Srikant, R.; Liu, Xin; Jiang, Chong (2015), <a rel="nofollow" class="external text" href="https://papers.nips.cc/paper/6008-algorithms-with-logarithmic-or-sublinear-regret-for-constrained-contextual-bandits">"Algorithms with Logarithmic or Sublinear Regret for Constrained Contextual Bandits"</a>, The 29th Annual Conference on Neural Information Processing Systems (NIPS), 28, Curran Associates: 433–441, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1504.06937">1504.06937</a>, <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2015arXiv150406937W">2015arXiv150406937W</a></cite>

</li>

<li id="cite_note-56"><a href="#cite_ref-56">^</a> <cite id="CITEREFBurtiniLoeppkyLawrence2015" class="citation arxiv cs1">Burtini, Giuseppe; Loeppky, Jason; Lawrence, Ramon (2015). "A Survey of Online Experiment Design with the Stochastic Multi-Armed Bandit". <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1510.00757">1510.00757</a> [<a rel="nofollow" class="external text" href="https://arxiv.org/archive/stat.ML">stat.ML</a>].</cite>

</li>

<li id="cite_note-57"><a href="#cite_ref-57">^</a> Seldin, Y., Szepesvári, C., Auer, P. and Abbasi-Yadkori, Y., 2012, December. Evaluation and Analysis of the Performance of the EXP3 Algorithm in Stochastic Environments. In EWRL (pp. 103–116).

</li>

<li id="cite_note-58"><a href="#cite_ref-58">^</a> Hutter, M. and Poland, J., 2005. <a rel="nofollow" class="external text" href="http://www.jmlr.org/papers/volume6/hutter05a/hutter05a.pdf">Adaptive online prediction by following the perturbed leader</a>. Journal of Machine Learning Research, 6 (Apr), pp.639–660.

</li>

<li id="cite_note-59"><a href="#cite_ref-59">^</a> Agrawal, Rajeev. The Continuum-Armed Bandit Problem. SIAM J. of Control and Optimization. 1995.

</li>

<li id="cite_note-60"><a href="#cite_ref-60">^</a> Besbes, O.; Gur, Y.; Zeevi, A. Stochastic multi-armed-bandit problem with non-stationary rewards. In Proceedings of the Advances in Neural Information Processing Systems, Montreal, QC, Canada, 8–13 December 2014; pp. 199–207<<a rel="nofollow" class="external free" href="https://proceedings.neurips.cc/paper/2014/file/903ce9225fca3e988c2af215d4e544d3-Paper.pdf">https://proceedings.neurips.cc/paper/2014/file/903ce9225fca3e988c2af215d4e544d3-Paper.pdf</a>>

</li>

<li id="cite_note-61"><a href="#cite_ref-61">^</a> Discounted UCB, Levente Kocsis, Csaba Szepesvári, 2006

</li>

<li id="cite_note-62"><a href="#cite_ref-62">^</a> <cite id="CITEREFGarivierMoulines2008" class="citation arxiv cs1">Garivier, Aurélien; Moulines, Eric (2008). "On Upper-Confidence Bound Policies for Non-Stationary Bandit Problems". <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/0805.3415">0805.3415</a> [<a rel="nofollow" class="external text" href="https://arxiv.org/archive/math.ST">math.ST</a>].</cite>

</li>

<li id="cite_note-63"><a href="#cite_ref-63">^</a> <cite id="CITEREFCavenaghiSottocornolaStellaZanker2021" class="citation journal cs1">Cavenaghi, Emanuele; Sottocornola, Gabriele; Stella, Fabio; Zanker, Markus (2021). <a rel="nofollow" class="external text" href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8004723">"Non Stationary Multi-Armed Bandit: Empirical Evaluation of a New Concept Drift-Aware Algorithm"</a>. Entropy. 23 (3): 380. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2021Entrp..23..380C">2021Entrp..23..380C</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.3390%2Fe23030380">10.3390/e23030380</a>. <a href="PMC_(identifier)" class="mw-redirect" title="PMC (identifier)">PMC</a> <a rel="nofollow" class="external text" href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8004723">8004723</a>. <a href="PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/33807028">33807028</a>.</cite>

</li>

<li id="cite_note-64"><a href="#cite_ref-64">^</a> Improving Online Marketing Experiments with Drifting Multi-armed Bandits, Giuseppe Burtini, Jason Loeppky, Ramon Lawrence, 2015 <<a rel="nofollow" class="external free" href="http://www.scitepress.org/DigitalLibrary/PublicationsDetail.aspx?ID=Dx2xXEB0PJE=&t=1">http://www.scitepress.org/DigitalLibrary/PublicationsDetail.aspx?ID=Dx2xXEB0PJE=&t=1</a>>

</li>

<cite id="CITEREFYueBroderKleinbergJoachims2012" class="citation cs2">Yue, Yisong; Broder, Josef; Kleinberg, Robert; Joachims, Thorsten (2012), "The K-armed dueling bandits problem", Journal of Computer and System Sciences, 78 (5): 1538–1556, <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.162.2764">10.1.1.162.2764</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.jcss.2011.12.028">10.1016/j.jcss.2011.12.028</a></cite>

</li>

<cite id="CITEREFYueJoachims2011" class="citation cs2">Yue, Yisong; Joachims, Thorsten (2011), "Beat the Mean Bandit", Proceedings of ICML'11</cite>

</li>

<li id="cite_note-Urvoy2013ICML:SAVAGE-67"><a href="#cite_ref-Urvoy2013ICML:SAVAGE_67-0">^</a> <cite id="CITEREFUrvoyClérotFéraudNaamane2013" class="citation cs2">Urvoy, Tanguy; Clérot, Fabrice; Féraud, Raphaël; Naamane, Sami (2013), <a rel="nofollow" class="external text" href="https://web.archive.org/web/20161002005005/http://jmlr.org/proceedings/papers/v28/urvoy13.pdf">"Generic Exploration and K-armed Voting Bandits"</a> (PDF), Proceedings of the 30th International Conference on Machine Learning (ICML-13), archived from <a rel="nofollow" class="external text" href="http://www.jmlr.org/proceedings/papers/v28/urvoy13.pdf">the original</a> (PDF) on 2016-10-02, retrieved 2016-04-29</cite>

</li>

<li id="cite_note-Zoghi2014ICML:RUCB-68"><a href="#cite_ref-Zoghi2014ICML:RUCB_68-0">^</a> <cite id="CITEREFZoghiWhitesonMunosRijke2014" class="citation cs2">Zoghi, Masrour; Whiteson, Shimon; Munos, Remi; Rijke, Maarten D (2014), <a rel="nofollow" class="external text" href="https://web.archive.org/web/20160326221859/http://jmlr.org/proceedings/papers/v32/zoghi14.pdf">"Relative Upper Confidence Bound for the $K$-Armed Dueling Bandit Problem"</a> (PDF), Proceedings of the 31st International Conference on Machine Learning (ICML-14), archived from <a rel="nofollow" class="external text" href="http://www.jmlr.org/proceedings/papers/v32/zoghi14.pdf">the original</a> (PDF) on 2016-03-26, retrieved 2016-04-27</cite>

</li>

<li id="cite_note-Gajane2015ICML:REX3-69"><a href="#cite_ref-Gajane2015ICML:REX3_69-0">^</a> <cite id="CITEREFGajaneUrvoyClérot2015" class="citation cs2">Gajane, Pratik; Urvoy, Tanguy; Clérot, Fabrice (2015), <a rel="nofollow" class="external text" href="https://web.archive.org/web/20150908110300/http://jmlr.org/proceedings/papers/v37/gajane15.pdf">"A Relative Exponential Weighing Algorithm for Adversarial Utility-based Dueling Bandits"</a> (PDF), Proceedings of the 32nd International Conference on Machine Learning (ICML-15), archived from <a rel="nofollow" class="external text" href="http://jmlr.org/proceedings/papers/v37/gajane15.pdf">the original</a> (PDF) on 2015-09-08, retrieved 2016-04-29</cite>

</li>

<cite id="CITEREFZoghiKarninWhitesonRijke2015" class="citation cs2">Zoghi, Masrour; Karnin, Zohar S; Whiteson, Shimon; Rijke, Maarten D (2015), "Copeland Dueling Bandits", Advances in Neural Information Processing Systems, NIPS'15, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1506.00312">1506.00312</a>, <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2015arXiv150600312Z">2015arXiv150600312Z</a></cite>

</li>

<li id="cite_note-Komiyama2015COLT:DB-71"><a href="#cite_ref-Komiyama2015COLT:DB_71-0">^</a> <cite id="CITEREFKomiyamaHondaKashimaNakagawa2015" class="citation cs2">Komiyama, Junpei; Honda, Junya; Kashima, Hisashi; Nakagawa, Hiroshi (2015), <a rel="nofollow" class="external text" href="https://web.archive.org/web/20160617164915/http://jmlr.org/proceedings/papers/v40/Komiyama15.pdf">"Regret Lower Bound and Optimal Algorithm in Dueling Bandit Problem"</a> (PDF), Proceedings of the 28th Conference on Learning Theory, archived from <a rel="nofollow" class="external text" href="http://jmlr.org/proceedings/papers/v40/Komiyama15.pdf">the original</a> (PDF) on 2016-06-17, retrieved 2016-04-27</cite>

</li>

<cite id="CITEREFWuLiu2016" class="citation cs2">Wu, Huasen; Liu, Xin (2016), "Double Thompson Sampling for Dueling Bandits", The 30th Annual Conference on Neural Information Processing Systems (NIPS), <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1604.07101">1604.07101</a>, <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2016arXiv160407101W">2016arXiv160407101W</a></cite>

</li>

<cite id="CITEREFCesa-BianchiGentileZappella2013" class="citation cs2">Cesa-Bianchi, Nicolo; Gentile, Claudio; Zappella, Giovanni (2013), A Gang of Bandits, Advances in Neural Information Processing Systems 26, NIPS 2013, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1306.0811">1306.0811</a></cite>

</li>

<cite id="CITEREFGentileLiZappella2014" class="citation cs2">Gentile, Claudio; Li, Shuai; Zappella, Giovanni (2014), "Online Clustering of Bandits", The 31st International Conference on Machine Learning, Journal of Machine Learning Research (ICML 2014), <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1401.8257">1401.8257</a>, <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2014arXiv1401.8257G">2014arXiv1401.8257G</a></cite>

</li>

<cite id="CITEREFLiAlexandrosGentile2016" class="citation cs2">Li, Shuai; Alexandros, Karatzoglou; Gentile, Claudio (2016), "Collaborative Filtering Bandits", The 39th International ACM SIGIR Conference on Information Retrieval (SIGIR 2016), <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1502.03473">1502.03473</a>, <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2015arXiv150203473L">2015arXiv150203473L</a></cite>

</li>

<cite id="CITEREFGai,_Y.Krishnamachari,_B.Jain,_R.2010" class="citation cs2">Gai, Y.; Krishnamachari, B.; Jain, R. (2010), "Learning multiuser channel allocations in cognitive radio networks: A combinatorial multi-armed bandit formulation", <a rel="nofollow" class="external text" href="http://www.academia.edu/download/30758682/DySPAN2010.pdf">2010 IEEE Symposium on New Frontiers in Dynamic Spectrum</a> (PDF), pp. 1–9</cite>

</li>

<li id="cite_note-chen2013combinatorial-77">^ <a href="#cite_ref-chen2013combinatorial_77-0">a</a> <a href="#cite_ref-chen2013combinatorial_77-1">b</a> <cite id="CITEREFChen,_WeiWang,_YajunYuan,_Yang2013" class="citation cs2">Chen, Wei; Wang, Yajun; Yuan, Yang (2013), "Combinatorial multi-armed bandit: General framework and applications", <a rel="nofollow" class="external text" href="https://web.archive.org/web/20161119193533/http://www.jmlr.org/proceedings/papers/v28/chen13a.pdf">Proceedings of the 30th International Conference on Machine Learning (ICML 2013)</a> (PDF), pp. 151–159, archived from <a rel="nofollow" class="external text" href="http://www.jmlr.org/proceedings/papers/v28/chen13a.pdf">the original</a> (PDF) on 2016-11-19, retrieved 2019-06-14</cite>

</li>

<cite id="CITEREFSantiago_Ontañón2017" class="citation cs2">Santiago Ontañón (2017), <a rel="nofollow" class="external text" href="https://www.jair.org/index.php/jair/article/download/11053/26230">"Combinatorial Multi-armed Bandits for Real-Time Strategy Games"</a>, Journal of Artificial Intelligence Research, 58: 665–702, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1710.04805">1710.04805</a>, <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2017arXiv171004805O">2017arXiv171004805O</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1613%2Fjair.5398">10.1613/jair.5398</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:8517525">8517525</a></cite>

</li>

</ol></div>

<div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .side-box{margin:4px 0;box-sizing:border-box;border:1px solid #aaa;font-size:88%;line-height:1.25em;background-color:var(--background-color-interactive-subtle,#f8f9fa);display:flow-root}.mw-parser-output .infobox .side-box{font-size:100%}.mw-parser-output .side-box-abovebelow,.mw-parser-output .side-box-text{padding:0.25em 0.9em}.mw-parser-output .side-box-image{padding:2px 0 2px 0.9em;text-align:center}.mw-parser-output .side-box-imageright{padding:2px 0.9em 2px 0;text-align:center}@media(min-width:500px){.mw-parser-output .side-box-flex{display:flex;align-items:center}.mw-parser-output .side-box-text{flex:1;min-width:0}}@media(min-width:720px){.mw-parser-output .side-box{width:238px}.mw-parser-output .side-box-right{clear:right;float:right;margin-left:1em}.mw-parser-output .side-box-left{margin-right:1em}}

/* end https://en.wikipedia.org/ */

</style>

<ul><li><cite id="CITEREFGuhaMunagalaShi2010" class="citation cs2">Guha, S.; Munagala, K.; Shi, P. (2010), "Approximation algorithms for restless bandit problems", Journal of the ACM, 58: 1–50, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/0711.3861">0711.3861</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1870103.1870106">10.1145/1870103.1870106</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:1654066">1654066</a></cite></li>

<li><cite id="CITEREFDayanikPowellYamazaki2008" class="citation cs2">Dayanik, S.; Powell, W.; Yamazaki, K. (2008), "Index policies for discounted bandit problems with availability constraints", Advances in Applied Probability, 40 (2): 377–400, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1239%2Faap%2F1214950209">10.1239/aap/1214950209</a></cite>.</li>

<li><cite id="CITEREFPowell2007" class="citation cs2">Powell, Warren B. (2007), "Chapter 10", Approximate Dynamic Programming: Solving the Curses of Dimensionality, New York: John Wiley and Sons, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-470-17155-4</bdi></cite>.</li>

<li><cite id="CITEREFRobbins1952" class="citation cs2"><a href="Herbert_Robbins" title="Herbert Robbins">Robbins, H.</a> (1952), "Some aspects of the sequential design of experiments", <a href="Bulletin_of_the_American_Mathematical_Society" title="Bulletin of the American Mathematical Society">Bulletin of the American Mathematical Society</a>, 58 (5): 527–535, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1090%2FS0002-9904-1952-09620-8">10.1090/S0002-9904-1952-09620-8</a></cite>.</li>

<li><cite id="CITEREFSuttonBarto1998" class="citation cs2">Sutton, Richard; Barto, Andrew (1998), <a rel="nofollow" class="external text" href="https://web.archive.org/web/20131211192714/http://webdocs.cs.ualberta.ca/~sutton/book/the-book.html">Reinforcement Learning</a>, MIT Press, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-262-19398-6</bdi>, archived from <a rel="nofollow" class="external text" href="http://webdocs.cs.ualberta.ca/~sutton/book/the-book.html">the original</a> on 2013-12-11</cite>.</li></ul>

<ul><li><cite id="CITEREFAllesiardo2014" class="citation cs2">Allesiardo, Robin (2014), "A Neural Networks Committee for the Contextual Bandit Problem", Neural Information Processing – 21st International Conference, ICONIP 2014, Malaisia, November 03-06,2014, Proceedings, Lecture Notes in Computer Science, vol. 8834, Springer, pp. 374–381, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/1409.8191">1409.8191</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-319-12637-1_47">10.1007/978-3-319-12637-1_47</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-319-12636-4</bdi>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:14155718">14155718</a></cite>.</li></ul>

<ul><li><cite id="CITEREFWeber1992" class="citation cs2">Weber, Richard (1992), "On the Gittins index for multiarmed bandits", <a href="Annals_of_Applied_Probability" title="Annals of Applied Probability">Annals of Applied Probability</a>, 2 (4): 1024–1033, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1214%2Faoap%2F1177005588">10.1214/aoap/1177005588</a>, <a href="JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/2959678">2959678</a></cite>.</li>

<li><cite id="CITEREFKatehakis,_M.C._Derman1986" class="citation cs2"><a href="Michael_N._Katehakis" class="mw-redirect" title="Michael N. Katehakis">Katehakis, M.</a>; C. Derman (1986), "Computing optimal sequential allocation rules in clinical trials", Adaptive statistical procedures and related topics, Institute of Mathematical Statistics Lecture Notes - Monograph Series, vol. 8, pp. 29–39, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1214%2Flnms%2F1215540286">10.1214/lnms/1215540286</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-940600-09-6</bdi>, <a href="JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/4355518">4355518</a>.</cite></li>

<li><cite id="CITEREFKatehakisVeinott,_Jr.1987" class="citation cs2"><a href="Michael_N._Katehakis" class="mw-redirect" title="Michael N. Katehakis">Katehakis, Michael N.</a>; Veinott, Jr., Arthur F. (1987), "The multi-armed bandit problem: decomposition and computation", <a href="Mathematics_of_Operations_Research" title="Mathematics of Operations Research">Mathematics of Operations Research</a>, 12 (2): 262–268, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1287%2Fmoor.12.2.262">10.1287/moor.12.2.262</a>, <a href="JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/3689689">3689689</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:656323">656323</a></cite></li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="https://github.com/fmr-llc/mabwiser">MABWiser</a>, <a href="Open-source" class="mw-redirect" title="Open-source">open-source</a> Python implementation of bandit strategies that supports context-free, parametric and non-parametric contextual policies with built-in parallelization and simulation capability.</li>

<li><a rel="nofollow" class="external text" href="https://mloss.org/software/view/415/">PyMaBandits</a>, open-source implementation of bandit strategies in Python and Matlab.</li>

<li><a rel="nofollow" class="external text" href="https://github.com/Nth-iteration-labs/contextual">Contextual</a>, open-source <a href="R_(programming_language)" title="R (programming language)">R</a> package facilitating the simulation and evaluation of both context-free and contextual Multi-Armed Bandit policies.</li>

<li><a rel="nofollow" class="external text" href="http://bandit.sourceforge.net">bandit.sourceforge.net Bandit project</a>, open-source implementation of bandit strategies.</li>

<li><a rel="nofollow" class="external text" href="https://github.com/jkomiyama/banditlib">Banditlib</a>, <a href="Open-source" class="mw-redirect" title="Open-source">open-source</a> implementation of bandit strategies in C++.</li>

<li><a rel="nofollow" class="external text" href="https://archive.today/20121212095047/http://www.cs.washington.edu/research/jair/volume4/kaelbling96a-html/node6.html">Leslie Pack Kaelbling and Michael L. Littman (1996). Exploitation versus Exploration: The Single-State Case</a>.</li>

<li>Tutorial: Introduction to Bandits: Algorithms and Theory. <a rel="nofollow" class="external text" href="http://techtalks.tv/talks/54451/">Part1</a>. <a rel="nofollow" class="external text" href="http://techtalks.tv/talks/54455/">Part2</a>.</li>

<li><a rel="nofollow" class="external text" href="https://feynmanlectures.caltech.edu/info/exercises/Feynmans_restaurant_problem.html">Feynman's restaurant problem</a>, a classic example (with known answer) of the exploitation vs. exploration tradeoff.</li>

<li><a rel="nofollow" class="external text" href="http://www.chrisstucchio.com/blog/2012/bandit_algorithms_vs_ab.html">Bandit algorithms vs. A-B testing</a>.</li>

<li><a rel="nofollow" class="external text" href="http://homes.di.unimi.it/~cesabian/Pubblicazioni/banditSurvey.pdf">S. Bubeck and N. Cesa-Bianchi A Survey on Bandits</a>.</li>

<li><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1508.03326">A Survey on Contextual Multi-armed Bandits</a>, a survey/tutorial for Contextual Bandits.</li>

<li><a rel="nofollow" class="external text" href="https://mpatacchiola.github.io/blog/2017/08/14/dissecting-reinforcement-learning-6.html">Blog post on multi-armed bandit strategies, with Python code</a>.</li>

<li><a rel="nofollow" class="external text" href="https://pavlov.tech/2019/03/02/animated-multi-armed-bandit-policies/">Animated, interactive plots</a> illustrating Epsilon-greedy, <a href="Thompson_sampling" title="Thompson sampling">Thompson sampling</a>, and Upper Confidence Bound exploration/exploitation balancing strategies.</li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Differentiable_computing254" style="padding:3px"><table class="nowraplinks hlist mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Differentiable_computing254" style="font-size:114%;margin:0 4em">Differentiable computing</div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Differentiable_function" title="Differentiable function">General</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Differentiable_programming" title="Differentiable programming">Differentiable programming</a></li>

<li><a href="Information_geometry" title="Information geometry">Information geometry</a></li>

<li><a href="Statistical_manifold" title="Statistical manifold">Statistical manifold</a></li>

<li><a href="Automatic_differentiation" title="Automatic differentiation">Automatic differentiation</a></li>

<li><a href="Neuromorphic_computing" title="Neuromorphic computing">Neuromorphic computing</a></li>

<li><a href="Pattern_recognition" title="Pattern recognition">Pattern recognition</a></li>

<li><a href="Ricci_calculus" title="Ricci calculus">Ricci calculus</a></li>

<li><a href="Computational_learning_theory" title="Computational learning theory">Computational learning theory</a></li>

<li><a href="Inductive_bias" title="Inductive bias">Inductive bias</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Hardware</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<li><a href="Memristor" title="Memristor">Memristor</a></li>

<li><a href="SpiNNaker" title="SpiNNaker">SpiNNaker</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Software libraries</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="TensorFlow" title="TensorFlow">TensorFlow</a></li>

<li><a href="PyTorch" title="PyTorch">PyTorch</a></li>

<li><a href="Keras" title="Keras">Keras</a></li>

<li><a href="Scikit-learn" title="Scikit-learn">scikit-learn</a></li>

<li><a href="Theano_(software)" title="Theano (software)">Theano</a></li>

<li><a href="MindSpore" title="MindSpore">MindSpore</a></li></ul>

</div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div>

<ul><li> Portals

<ul><li><a href="Portal%3AComputer_programming" title="Portal:Computer programming">Computer programming</a></li>

<li><a href="Portal%3ATechnology" title="Portal:Technology">Technology</a></li></ul></li></ul>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-07-30" href="https://en.wikipedia.org/wiki/?title=Multi-armed_bandit&oldid=1303423425">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>